codeforces 666A (DP)

题目链接:http://codeforces.com/problemset/problem/666/A

思路:dp[i][0]表示第a[i-1]~a[i]组成的字符串是否可行,dp[i][1]表示第a[i-2]~a[i]组成的字符串是否可行,显然dp[len-2][0(1)]必定不可行。

转移方程:

dp[i][0] = dp[i+3][1] || dp[i+2][0] && (tmp1 != tmp2);
dp[i][1] = dp[i+2][0] || dp[i+3][1] && (tmp1 != tmp2);
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
typedef long long ll;
char a[N];
string ans[N<<1];
string tmp1 ,tmp2;
bool dp[N][2];
int cur ,num = 1;
int main()
{
scanf("%s",a);
int len = strlen(a);
if(len <= 6)
{
printf("0\n");
return 0;
}
dp[len-1][0] = 1;
tmp1 = "";
tmp1 += a[len-2];
tmp1 += a[len-1];
ans[cur++] = tmp1;
if(len > 7)
{
dp[len-1][1] = 1;
tmp1 = "";
tmp1 += a[len-3];
tmp1 += a[len-2];
tmp1 += a[len-1];
ans[cur++] = tmp1;
}
for(int i = len - 3 ;i >= 6 ;i--)
{
tmp1 = "";
tmp1 += a[i-1];
tmp1 += a[i];
tmp2 = "";
tmp2 += a[i+1];
tmp2 += a[i+2];
dp[i][0] = dp[i+3][1] || dp[i+2][0] && (tmp1 != tmp2);
if(dp[i][0])
ans[cur++] = tmp1; if(i == 6)
continue; tmp1 = "";
tmp1 += a[i-2];
tmp1 += a[i-1];
tmp1 += a[i];
tmp2 = "";
tmp2 += a[i+1];
tmp2 += a[i+2];
tmp2 += a[i+3];
dp[i][1] = dp[i+2][0] || dp[i+3][1] && (tmp1 != tmp2);
if(dp[i][1])
ans[cur++] = tmp1;
}
sort(ans ,ans + cur);//排序
for(int i = 1 ; i < cur ; i++)
{
if(ans[i] != ans[i-1])//并去重
num++;
}
printf("%d\n",num);
cout<<ans[0]<<"\n";
for(int i = 1 ; i < cur ; i++)
{
if(ans[i] != ans[i-1])
cout<<ans[i]<<"\n";
}
return 0;
}
上一篇:Dubbo相关博文整理


下一篇:Android 自绘TextView解决提前换行问题,支持图文混排