A 回文串的最小划分
题意：给出长度不超过1000的字符串，把它分割成若干个回文字串，求能分成的最少字串数。
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
using namespace std;
const int mod = 1e9 + ;
const int maxn = + ;
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+;
int L = strlen(s+);
for(int i=;i <= L;i++) dp[i] = i; for(int i=;i <= L;i++)
{
for(int j=i,k=i; j <= L && k > ;j++ ,k--)//这种是aabcc形的回文串
{
if(s[j] == s[k] )
dp[j] = min(dp[j],dp[k-] +);
else
break;
}
for(int j=i+,k=i; j <= L && k > ;j++,k--)//这种是aabb形的回文串
{
if(s[j] == s[k] )
dp[j] = min(dp[j],dp[k-] +);
else
break;
}
}
cout<< dp[L]<<endl;
}
return ;
}
A
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 + ;
const int maxn = + ;
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 = ;
int l = ,r = len-; //这里注意 右区间是 len-1
while ( l <= r)
{
int mid = (l+r)/;
if(B[mid] >= k ) ans = mid,r = mid-; //如果k<= B[mid] 往左边查找
else l = mid +;
}
return ans ;
} void Lis(int *s,int *a) //a数组存取到i位 的最长递增子序列个数
{
B[] = s[];
len = ;
for(int i=;i < n;i++)
{
if(s[i] > B[len-])
{
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=;i < n;i++){
cin >> s1[i];
s2[n--i] = s1[i];//把序列倒着读
}
Lis(s1,a1), Lis(s2,a2); //longest increasing substring 最长递增子序列函数
int ans = ;
for(int i=;i < n;i++)
{
ans = max(ans, min(a1[i],a2[n--i])); //ans 是 ans 与 当前位 左右最长递增 和 最长递减的较小者
}
cout<< *ans - <<endl;
}
return ;
}
B
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 + ;
const int maxn = + ;
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+)
{
int L = strlen(s+);
for(int i=L;i >= ;i--) //这个查找是从 左下到右上进行的
{
dp[i][i] = ;//i到i不用删除
path[i][i] = s[i];//i到i的最长回文子序列就是本身
for(int j=i+;j <= L;j++)
{
if(s[i] == s[j]) //就是 s[i][j]这两个字符相同 可以构成回文串
{
dp[i][j] = dp[i+][j-]; //所以这时候 需要删除的就是左下角的
path[i][j] = s[i] + path[i+][j-] +s[j];//只有这一步是构造回文串的
}
else if(dp[i+][j] > dp[i][j-])
{
dp[i][j] = dp[i][j-] + ;
path[i][j] = path[i][j-];
}
else if(dp[i+][j] < dp[i][j-])
{
dp[i][j] = dp[i+][j] + ;
path[i][j] = path[i+][j];
}
else{
dp[i][j] = dp[i+][j] + ;
path[i][j] = min(path[i][j-], path[i+][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[][L] <<endl;
}
return ;
}
C
思路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 + ;
const int maxn = + ;
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+)
{
int L = strlen(s1+);
strcpy(s2+,s1+);
reverse(s2+,s2++L); for(int i=;i <= L;i++)
{
for(int j=;j <= L;j++)
{
if(s1[i] == s2[j]){
dp[i][j].len = dp[i-][j-].len+;
dp[i][j].s = dp[i-][j-].s + s1[i];
}
else if(dp[i-][j].len < dp[i][j-].len){
dp[i][j].len = dp[i][j-].len;
dp[i][j].s = dp[i][j-].s;
}
else if(dp[i-][j].len > dp[i][j-].len){
dp[i][j].len = dp[i-][j].len;
dp[i][j].s = dp[i-][j].s;
}
else{
dp[i][j].len = dp[i-][j].len;
dp[i][j].s = min( dp[i-][j].s ,dp[i][j-].s);
}
}
}
string s = dp[L][L].s;
int l =dp[L][L].len;
if( l & ) //l是奇数，所以字符串长度是偶数
{
for(int i=;i<l/;i++)
cout<<s[i];
for(int i=l/;i>=;i--)
cout<<s[i];
cout<<endl;
}
else{
for(int i=;i<l/;i++)
cout<<s[i];
for(int i=l/-;i>=;i--)
cout<<s[i];
cout<<endl;
} }
return ;
}
C_LCS
D.UVA11795——Mega Mans Missions （还不太会）
题意：
给出初始武器和消灭每个机器人所能获得的武器，消灭每个机器人需要对应的武器。问消灭所有机器人的方法一共有多少种。（N<=16）
分析：
可以用一个16位的二进制数表示出当前机器人的存在情况，即一个状态。
首先预处理出每个状态下所能获得的武器。
然后依据利用DP的方式求解到达每种状态的方法数。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; const int maxn = ;
int attack[maxn]; //表示每个机器人能干掉的
int can_attack[<<]; //表示每个状态能干掉的
long long dp[<<]; //用来统计每种状态的种数
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 = ;
cin >> T;
while (T--)
{
cin >> n;
for(int i=; i <= n;i++)
{
attack[i] = ;//刚开始 二进制位都初始为0
cin >> s;
for(int j =; j < n; j++)
{
if(s[j] == '')
attack[i] |= ( << j);//如果这一位可以击破 就给他赋值为1
}
}
//for(int i=0;i<=n;i++)
//cout<< attack[i] << " ";
int total = ( << n) -;
for(int st = ;st <= total; st++)
{
can_attack[st] = attack[];//记录的刚开始的状态
for(int i=; i<=n; i++)
{
int j=i-;
if( st & ( << j) ) //如果这个状态可以攻击j
{
can_attack[st] |= attack[i];//再把攻击完j 获得武器加上
}
}
}
memset(dp,,sizeof(dp));
dp[] = ;
for(int st = ;st <= total; st++)
{
for(int i = ;i < n;i++)
{
if(st & ( << i))//如果st的这种状态能够干掉i，
{
if( can_attack[st ^ (<<i)] & ( << i) )//那么要由不能干掉i的状态转移过来,即st ^ (1<<i)
{
dp[st] += dp[st ^ (<<i)];
}
}
}
}
cout<<"Case "<<cas++ <<": "<<dp[total] <<endl;
}
return ;
}
D
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[][], vis[][][];
ll dp[][][];//dp[i][j][k]就表示到第i行第j列之后和为k的方法数
string ans; void initial ()
{
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
mp[i][j] = ;
}
}
ans.clear();
start = -;
}
void read()//记录整个地图
{
int c = N;
for(int i=;i < *N-;i++)
{
for(int j=;j < c;j++)
cin >> mp[i][j];
if(i < N-) c--;
else c++;
}
} ll DP(int k, int p, int s, int c, string dir)//从mp[k][p]和为s c表示当前行的个数 dir 表示记录的方位
{
if(s < ) return ; //这就说明没有这种情况 为0
if(k >= *N - ) //这就已经到最后一行了
{
if(s == )
{
if(ans.length() == ) ans = dir; //因为是按照顺序来的 所以第一个被访问到的 肯定就是字典序最小的
return ;
}
return ;
}
if( vis[k][p][s] == v ) return dp[k][p][s]; //这个用来表示 访问过没有 ==v 是为了更好的判断每个样例
vis[k][p][s] = v;
dp[k][p][s] = ;
if(k < N-)//这是从大往小走 然后先往p-1 走然后在走p
{
c--;
if(p- >= ) dp[k][p][s] += DP(k+,p-,s-mp[k+][p-],c,dir+"L");
if(p < c) dp[k][p][s] += DP(k+,p,s-mp[k+][p],c,dir+"R");
}
else//从小往大 先往p 然后p+1
{
c++;
dp[k][p][s] += DP(k+,p,s-mp[k+][p],c,dir+"L");
if(p+ < c) dp[k][p][s] += DP(k+,p+,s-mp[k+][p+],c,dir+"R");
}
return dp[k][p][s];
} void solve ()
{
ll sum = ;
if(S <= )//351 是因为 （20+19） * 9;
{
for(int i=;i < N;i++){
sum += DP(, i, S-mp[][i], N, "");
if(S-mp[][i] >= && dp[][i][S-mp[][i]] > &&start == - )//这个用来更新start的状态
start = i;//只更新了最小的 更新完以后start != -1 了 所以没事...
}
}
cout<< sum <<endl;
if(sum == )
cout<<endl;
else
cout<< start <<" " <<ans.c_str() <<endl; } int main()
{
std::ios::sync_with_stdio(false);
v = ;
while (cin>> N >> S && N+S)
{
initial();
read();
solve();
v++;
}
return ;
}
E_ DFS实现版本
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 = ;
int k;
char str[maxn];
int f[maxn][maxn]; // f[i][j]: 第i块的第j位排在最后一位的最少chunks
bool vis []; 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=; i<len/k; i++)//分块
{
int chunks = ;
memset(vis , , sizeof(vis)) ;
for (int j = i * k; j < (i+)*k; j++)
vis[ str[j] ] = ;//标记有这个字符 for(int j='a'; j <='z';j++)
if( vis[j] ) ++chunks;//有多少字符 就有多少chunks
if(i == )
{
for(int j=; j<k; j++)
f[i][j] = chunks;//把第1个分块 不管怎么排，都是有chunks个
continue;
}//no problem for(int j=; j<k; j++)
{
int rear = i*k + j;//这个i*k 是 第i个分块的情况
for(int l= ; l<k ; l++)
{
int pre = (i-)*k+l;//这是i-1分块的情况
if(vis[ str[pre] ] && (chunks == || 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-][l] + chunks -);
else
{
f[i][j] = min(f[i][j],f[i-][l] + chunks);
}
}
} }
int ans = INF;
for(int i=;i<k;i++)
ans = min(ans,f[len/k -][i]);
cout<< ans <<endl;
}
return ;
}
F 充分理解dp方程的含义