大德通众包网站建设,网站seo案例,创意设计公司业务范围,搜狗推广排名回文字符串 时间限制#xff1a;3000 ms | 内存限制#xff1a;65535 KB难度#xff1a;4描写叙述所谓回文字符串#xff0c;就是一个字符串。从左到右读和从右到左读是全然一样的。比方aba。当然#xff0c;我们给你的问题不会再简单到推断一个字符串是不是… 回文字符串 时间限制3000 ms | 内存限制65535 KB 难度4 描写叙述所谓回文字符串就是一个字符串。从左到右读和从右到左读是全然一样的。比方aba。当然我们给你的问题不会再简单到推断一个字符串是不是回文字符串。如今要求你给你一个字符串可在任何位置加入字符。最少再加入几个字符能够使这个字符串成为回文字符串。 输入第一行给出整数N0N100 接下来的N行。每行一个字符串每一个字符串长度不超过1000.输出每行输出所需加入的最少字符数例子输入 1
Ab3bd 例子输出 2 来源 IOI 2000 開始看到这道题的时候一时想不出用什么非常好的方法来做。看到分类是在动态规划也大致往这方面想。看了别人的思路。顿时茅塞顿开啊直接把给定的字符串倒转然后再和原字符串一起求他们的最长公共序列然后再拿字符串的长度减去他们的最长公共序列的长度得到的就是要加入的最小的字符数。想到了这个地方这个题目就非常好解啦直接用LIC水过状态方程式也和前面做过的题一样 #include cstdio
#include cstring
#define max(a,b) ab?a:b
const int maxn1001;
char a[maxn],b[maxn];
int dp[maxn][maxn];//昨天晚上把DP的类型设置成了char型然后提交一直wa刷屏了。。。不应该啊。 int main() { int n,i,j,len; scanf(%d,n); while(n--) { memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); scanf(%s,a); lenstrlen(a); for(ilen-1,j0;i0;i--) b[j]a[i]; for(i1;ilen;i) { for(j1;jlen;j) { if(a[i-1]b[j-1]) dp[i][j]dp[i-1][j-1]1;//递推关系 else dp[i][j]max(dp[i-1][j],dp[i][j-1]); } } printf(%d\n,len-dp[len][len]); } } 看到别人的写的用了还有一种思路也是动态规划。可是递推关系有一点不同有点没看懂 省去了倒转的环节
#includestdio.h
#includestring.h int f[1005][1005]; int main()
{ int n; scanf(%d,n); while (n--) { char s[1005]; scanf(%s,s); int k,i,j,lstrlen(s); for (i0;il;i) f[i][i]0; for (k2;kl;k) { for (i0;il-k;i) { int pik-1; if (s[i]s[p]) { f[i][p]f[i1][p-1]; } else { f[i][p]1(f[i][p-1]f[i1][p]?f[i][p-1]:f[i1][p]); } } } printf(%d\n,f[0][l-1]); memset(f,0,sizeof(f)); } return 0; } 看到别人的最优代码内存占用的非常小。值得学习另一种滚动数组。好像能够节约内存。还没有接触过 #includestdio.h
#includestring.h
using namespace std;
int m[1000],i,j,t1,t2,len;
char s[1001];
int main() {int N;scanf(%d,N);while(N--){scanf(%s,s);lenstrlen(s);for(ilen-1;i0;i--){m[i]0;t1m[i];for(ji1;jlen;j){t2m[j];if(s[i]s[j])m[j]t1;elsem[j]m[j-1]m[j]?m[j-1]1:m[j]1;t1t2;}}printf(%d\n,m[len-1]);}
} 转载于:https://www.cnblogs.com/wzjhoutai/p/7222299.html
