正文
新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛）- Red Rover
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
链接：https://www.nowcoder.com/acm/contest/116/A
来源：牛客网
输入描述:
Input consists of a single line containing a string made up of the letters N, S, E, and W representing the route to transmit to the rover. The maximum length of the string is 100.
输出描述:
Display the minimum number of characters needed to encode the route.
Display the minimum number of characters needed to encode the route.
输入例子:
WNEENWEENEENE
输出例子:
10
-->
示例1
输入
WNEENWEENEENE
WNEENWEENEENE
输出
10
10
题意：给你一个由NSEW四个字符组成的字符串你可以选择一个子串用M表示，这是字符串的长度就变成了改变后的长度加上M的长度，题目让我们求出最小的长度（注意不能整个变成一个W）
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int sum=;
struct node{
string str;
int len;
};
vector<node>ve;
map<string,int>mp;
int main()
{
int n;
string s;
cin>>s;
int len=s.length();
int minn=len;
for(int i=;i<len;i++){
for(int j=i+;j<len;j++){
string now=s.substr(i,j-i);
int be=,cnt=;
int num=;
while(cnt!=-){
cnt=s.find(now,be);
be=cnt+now.length();
if(cnt!=-)num++;
}
if(minn>len-(num*now.length())+num+now.length()){
minn=len-(num*now.length())+num+now.length();
}
}
}
cout<<minn<<endl;
return ;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int sum=;
struct node{
string str;
int len;
};
vector<node>ve;
map<string,int>mp;
int main()
{
int n;
string s;
cin>>s;
int len=s.length();
int minn=len;
for(int i=;i<len;i++){
for(int j=i+;j<len;j++){
string now=s.substr(i,j-i);
int be=,cnt=;
int num=;
while(cnt!=-){
cnt=s.find(now,be);
be=cnt+now.length();
if(cnt!=-)num++;
}
if(minn>len-(num*now.length())+num+now.length()){
minn=len-(num*now.length())+num+now.length();
}
}
}
cout<<minn<<endl;
return ; }
