A 回文串的最小划分
题意：给出长度不超过1000的字符串，把它分割成若干个回文字串，求能分成的最少字串数。
#include <iostream> #include <cstdio> #include <string.h> #include <string> using namespace std; const int mod = 1e9 + 7; const int maxn = 1000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; int dp[maxn]; //根据回文串的特性，两边根据中心对称。于是我们扫描回文串的每个中心，寻找他的回文串，用DP来记录更新 //dp[n] 表示到n为止可以分割出多少个回文串 //如果[Left , Right]是回文串， //dp[Right] = min(dp[ Right ] , dp[Left-1] + 1); int main() { int n; cin >> n; while ( n-- ) { char s[maxn]; cin >> s+1; int L = strlen(s+1); for(int i=1;i <= L;i++) dp[i] = i; for(int i=1;i <= L;i++) { for(int j=i,k=i; j <= L && k > 0 ;j++ ,k--)//这种是aabcc形的回文串 { if(s[j] == s[k] ) dp[j] = min(dp[j],dp[k-1] +1); else break; } for(int j=i+1,k=i; j <= L && k > 0 ;j++,k--)//这种是aabb形的回文串 { if(s[j] == s[k] ) dp[j] = min(dp[j],dp[k-1] +1); else break; } } cout<< dp[L]<<endl; } return 0; }
B - LIS变形
题意：给定一串数字，求一个子串满足一下要求：子串的长度是L=2*n+1，前n+1个数字是严格的递增序列，后n+1个数字是严格的递减序列，例如123454321就是满足要求的一个子串，
输出满足要求的最长的L
思路：正着走一遍LIS，再倒着走一遍LIS，a1[i] 表示正着走的 到i的最长递增子序列的长度，a2[i] 表示倒着着走的 到i的最长递增子序列的长度
//本题 二分 + LIS 需要巩固一下
#include <iostream> #include <cstdio> using namespace std; const int mod = 1e9 + 7; const int maxn = 10000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; int n,len; int s1[maxn],s2[maxn]; int a1[maxn],a2[maxn]; int B[maxn]; int b_s(int k) { int ans = 0; int l = 0,r = len-1; //这里注意 右区间是 len-1 while ( l <= r) { int mid = (l+r)/2; if(B[mid] >= k ) ans = mid,r = mid-1; //如果k<= B[mid] 往左边查找 else l = mid +1; } return ans ; } void Lis(int *s,int *a) //a数组存取到i位 的最长递增子序列个数 { B[0] = s[0]; len = 1; for(int i=0;i < n;i++) { if(s[i] > B[len-1]) { B[len++] = s[i]; } else{ int pos = b_s (s[i]); //二分找s[i]的插入位置 B[pos] = s[i]; } a[i] = len; } } int main() { while (cin >> n) { for(int i=0;i < n;i++){ cin >> s1[i]; s2[n-1-i] = s1[i];//把序列倒着读 } Lis(s1,a1), Lis(s2,a2); //longest increasing substring 最长递增子序列函数 int ans = 0; for(int i=0;i < n;i++) { ans = max(ans, min(a1[i],a2[n-1-i])); //ans 是 ans 与 当前位 左右最长递增 和 最长递减的较小者 } cout<< 2*ans -1 <<endl; } return 0; }
C - 区间dp or LCS的变形
题意：给你一个字符串， 求最长的回文子序列， 若答案不唯一， 则输出字典序最小的
思路1：区间dp， dp[i][j]表示字符串s[i]到s[j]构成回文子序列学删除的最小字符数, path[i][j] 字符串s[i]到s[j]可构成的最长回文子序列
#include <iostream> #include <cstdio> #include <string.h> #include <string> using namespace std; const int mod = 1e9 + 7; const int maxn = 1000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; //区间dp dp[i][j] 表示字符串s[i]到s[j]构成回文子序列学删除的最小字符数 //path[i][j] 字符串s[i]到s[j]可构成的最长回文子序列 string path[maxn][maxn]; int dp[maxn][maxn]; char s[maxn]; int main() { while (cin >> s+1) { int L = strlen(s+1); for(int i=L;i >= 1;i--) //这个查找是从 左下到右上进行的 { dp[i][i] = 0;//i到i不用删除 path[i][i] = s[i];//i到i的最长回文子序列就是本身 for(int j=i+1;j <= L;j++) { if(s[i] == s[j]) //就是 s[i][j]这两个字符相同 可以构成回文串 { dp[i][j] = dp[i+1][j-1]; //所以这时候 需要删除的就是左下角的 path[i][j] = s[i] + path[i+1][j-1] +s[j];//只有这一步是构造回文串的 } else if(dp[i+1][j] > dp[i][j-1]) { dp[i][j] = dp[i][j-1] + 1; path[i][j] = path[i][j-1]; } else if(dp[i+1][j] < dp[i][j-1]) { dp[i][j] = dp[i+1][j] + 1; path[i][j] = path[i+1][j]; } else{ dp[i][j] = dp[i+1][j] + 1; path[i][j] = min(path[i][j-1], path[i+1][j]); } } /* for(int a = 1;a<=L;a++) { for(int b= 1;b<=L;b++) { cout<< path[a][b]<<" "; } cout<<endl; } cout<<"----------" <<endl; */ } cout << path[1][L] <<endl; } return 0; }
思路2：转化为lcs， 用结构体进行保存，一维只长度， 一维指构成的字符串
我们都知道把一个字符串逆序后和原字符串进最长公共子序列，可以计算出它的最长回文串长度。这题不仅要输出回文串，而且还要求是字典序最小的，所以挺难搞的。
设str1是正序字符串，str2是逆序后的字符串
f[i][j].len 表示str1的前i位，str2的前j位，最长公共子串的长度
f[i][j].str 表示str1的前i位，str2的前j位，最长公共子串的最小字典序的字符串
状态转移和正常的LCS差不多，只不过增加了记录字典序最小的字符串
但是最终的f[i][j].str却并不一定是答案，因为计算出来的最长公共子序列不一定就是回文串
例如：
kfclbckibbibjccbej
jebccjbibbikcblcfk
bcibbibc是他们的LCS，但是却不是回文串
但是它的前len/2个一定是回文串的前半部分
#include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; using namespace std; const int mod = 1e9 + 7; const int maxn = 1000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; struct node{ int len; string s; }dp[maxn][maxn]; char s1[maxn],s2[maxn]; int main () { while (cin >> s1+1) { int L = strlen(s1+1); strcpy(s2+1,s1+1); reverse(s2+1,s2+1+L); for(int i=1;i <= L;i++) { for(int j=1;j <= L;j++) { if(s1[i] == s2[j]){ dp[i][j].len = dp[i-1][j-1].len+1; dp[i][j].s = dp[i-1][j-1].s + s1[i]; } else if(dp[i-1][j].len < dp[i][j-1].len){ dp[i][j].len = dp[i][j-1].len; dp[i][j].s = dp[i][j-1].s; } else if(dp[i-1][j].len > dp[i][j-1].len){ dp[i][j].len = dp[i-1][j].len; dp[i][j].s = dp[i-1][j].s; } else{ dp[i][j].len = dp[i-1][j].len; dp[i][j].s = min( dp[i-1][j].s ,dp[i][j-1].s); } } } string s = dp[L][L].s; int l =dp[L][L].len; if( l & 1) //l是奇数，所以字符串长度是偶数 { for(int i=0;i<l/2;i++) cout<<s[i]; for(int i=l/2;i>=0;i--) cout<<s[i]; cout<<endl; } else{ for(int i=0;i<l/2;i++) cout<<s[i]; for(int i=l/2-1;i>=0;i--) cout<<s[i]; cout<<endl; } } return 0; }
D.UVA11795——Mega Mans Missions （还不太会）
题意：
给出初始武器和消灭每个机器人所能获得的武器，消灭每个机器人需要对应的武器。问消灭所有机器人的方法一共有多少种。（N<=16）
分析：
可以用一个16位的二进制数表示出当前机器人的存在情况，即一个状态。
首先预处理出每个状态下所能获得的武器。
然后依据利用DP的方式求解到达每种状态的方法数。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn = 20; int attack[maxn]; //表示每个机器人能干掉的 int can_attack[1<<16]; //表示每个状态能干掉的 long long dp[1<<16]; //用来统计每种状态的种数 char s[maxn]; int n; int main () { //freopen("C:\Users\ixiao\Desktop\in.txt","r",stdin); //freopen("C:\Users\ixiao\Desktop\out.txt","w",stdout); int T; int cas = 1; cin >> T; while (T--) { cin >> n; for(int i=0; i <= n;i++) { attack[i] = 0;//刚开始 二进制位都初始为0 cin >> s; for(int j =0; j < n; j++) { if(s[j] == '1') attack[i] |= (1 << j);//如果这一位可以击破 就给他赋值为1 } } //for(int i=0;i<=n;i++) //cout<< attack[i] << " "; int total = (1 << n) -1; for(int st = 0;st <= total; st++) { can_attack[st] = attack[0];//记录的刚开始的状态 for(int i=1; i<=n; i++) { int j=i-1; if( st & (1 << j) ) //如果这个状态可以攻击j { can_attack[st] |= attack[i];//再把攻击完j 获得武器加上 } } } memset(dp,0,sizeof(dp)); dp[0] = 1; for(int st = 1;st <= total; st++) { for(int i = 0;i < n;i++) { if(st & (1 << i))//如果st的这种状态能够干掉i， { if( can_attack[st ^ (1<<i)] & (1 << i) )//那么要由不能干掉i的状态转移过来,即st ^ (1<<i) { dp[st] += dp[st ^ (1<<i)]; } } } } cout<<"Case "<<cas++ <<": "<<dp[total] <<endl; } return 0; }
E uva 10564 Paths through the Hourglass（DP）
题意：
有一个沙漏，如下图所示。你可以从第一行的任意一格开始往下走，向左下方或者右下方走，但不能走出沙漏。你的目标是让沿途所有经过的整数之和恰好为一个整数 s ，求出符合上述条件的路径总数，以及打印一条路径。如果有多条路径，选择起点编号最小的，每一行的格子编号从 0 开始。如果仍然有多个解，移动序列(L代表左移，R代表右移)的字典序应最小。如果不存在可行的路径，输出 0，并且在 0 的下面输出一行空行。
思路：
待续~
看着别人的题解实现一遍 就有些感觉了 他这个用了 记忆化数组....问题是代码好恶心 ...等以后变得更强了 自己再写写把
#include <iostream> #include <cstring> #include <string> #include <cstdio> using namespace std; typedef long long ll; int start, N, S, v, mp[50][50], vis[50][50][510]; ll dp[50][50][510];//dp[i][j][k]就表示到第i行第j列之后和为k的方法数 string ans; void initial () { for(int i=0; i<50; i++) { for(int j=0; j<50; j++) { mp[i][j] = 0; } } ans.clear(); start = -1; } void read()//记录整个地图 { int c = N; for(int i=0;i < 2*N-1;i++) { for(int j=0;j < c;j++) cin >> mp[i][j]; if(i < N-1) c--; else c++; } } ll DP(int k, int p, int s, int c, string dir)//从mp[k][p]和为s c表示当前行的个数 dir 表示记录的方位 { if(s < 0) return 0; //这就说明没有这种情况 为0 if(k >= 2*N - 2) //这就已经到最后一行了 { if(s == 0) { if(ans.length() == 0) ans = dir; //因为是按照顺序来的 所以第一个被访问到的 肯定就是字典序最小的 return 1; } return 0; } if( vis[k][p][s] == v ) return dp[k][p][s]; //这个用来表示 访问过没有 ==v 是为了更好的判断每个样例 vis[k][p][s] = v; dp[k][p][s] = 0; if(k < N-1)//这是从大往小走 然后先往p-1 走然后在走p { c--; if(p-1 >= 0) dp[k][p][s] += DP(k+1,p-1,s-mp[k+1][p-1],c,dir+"L"); if(p < c) dp[k][p][s] += DP(k+1,p,s-mp[k+1][p],c,dir+"R"); } else//从小往大 先往p 然后p+1 { c++; dp[k][p][s] += DP(k+1,p,s-mp[k+1][p],c,dir+"L"); if(p+1 < c) dp[k][p][s] += DP(k+1,p+1,s-mp[k+1][p+1],c,dir+"R"); } return dp[k][p][s]; } void solve () { ll sum = 0; if(S <= 351)//351 是因为 （20+19） * 9; { for(int i=0;i < N;i++){ sum += DP(0, i, S-mp[0][i], N, ""); if(S-mp[0][i] >= 0 && dp[0][i][S-mp[0][i]] > 0 &&start == -1 )//这个用来更新start的状态 start = i;//只更新了最小的 更新完以后start != -1 了 所以没事... } } cout<< sum <<endl; if(sum == 0) cout<<endl; else cout<< start <<" " <<ans.c_str() <<endl; } int main() { std::ios::sync_with_stdio(false); v = 1; while (cin>> N >> S && N+S) { initial(); read(); solve(); v++; } return 0; }
uva 11552 - Fewest Flops ( 多维dp )
题意：
给一个字符串，把它分为ｋ块，例如字符串“helloworld”分成2块，"hello", "world"
每一块里面的字母可以任意的排序。
最终字符串， 连续的一样的字母算作一个chunk，问总chunks最少是多少？
思路：
f[i][j]: 第i块的第j位排在最后一位的最少chunks
对于每个单独的一块，它的chunks就是等于出现的不同字母数 第i块的chunks记做 chunks[i]
如果第i-1块的最后一位和第i块的第一位是一样的，那么可以合并这两个，总chunks可以减少一个
f[i][j] = min{ 如果i-1块的第k位和i块的第一位不同: f[i-1][k]+chunks[i],
如果i-1块的第k位和i块的第一位相同: f[i-1][k]+chunks[i]-1 }
//心静一下 #include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1010; int k; char str[maxn]; int f[maxn][maxn]; // f[i][j]: 第i块的第j位排在最后一位的最少chunks bool vis [300]; int main () { std::ios::sync_with_stdio(false); int t; cin >> t; while (t--) { cin>> k >> str; int len = strlen(str); memset(f, INF, sizeof(f) ); for(int i=0; i<len/k; i++)//分块 { int chunks = 0; memset(vis , 0, sizeof(vis)) ; for (int j = i * k; j < (i+1)*k; j++) vis[ str[j] ] = 1;//标记有这个字符 for(int j='a'; j <='z';j++) if( vis[j] ) ++chunks;//有多少字符 就有多少chunks if(i == 0) { for(int j=0; j<k; j++) f[i][j] = chunks;//把第1个分块 不管怎么排，都是有chunks个 continue; }//no problem for(int j=0; j<k; j++) { int rear = i*k + j;//这个i*k 是 第i个分块的情况 for(int l=0 ; l<k ; l++) { int pre = (i-1)*k+l;//这是i-1分块的情况 if(vis[ str[pre] ] && (chunks == 1 || str[pre] != str[rear])) /* vis[ str[pre] ] 说明第i-1个分块 里的pre字符在当前第i个分块里面出现过 chunks=1就说明 比如第i-1个分块是 haoran 而第i个分块是nn 所以此时直接-1就可以了 而str[pre] != str[rear] 表示rear不与pre相等 就说明当前rear做第i个分块的尾部 而与pre相等的字符做头部 这样就可以合并一个了 重点是理解f[i][j] 记录的东西是什么 这道题就好做了 */ f[i][j] = min(f[i][j], f[i-1][l] + chunks -1); else { f[i][j] = min(f[i][j],f[i-1][l] + chunks); } } } } int ans = INF; for(int i=0;i<k;i++) ans = min(ans,f[len/k -1][i]); cout<< ans <<endl; } return 0; }