动态规划训练第一阶段（for初学者）
A WordStack
题目链接：http://poj.org/problem?id=2817
一些二进制的基本知识
判断j是否属于集合i：i&(1<<j)
在集合i中去除j：i-(1<<j)或者i&(!(1<<j)) i^(1<<j)
在集合i中加入点j：i|(1<<j);
先预处理出len[i][j]表示第i个字符串与第j个字符串组合能匹配的最大字符数
用一个数的二进制来表示那些字符串，那些字符串还没有选，即二进制位为1的表示已经选了，为0的表示还没有选
Dp[i][j]代表当选取的字符串为i状态，且最后一个选取的字符串是第j个字符串时的最优值
状态转移：枚举某个状态时，枚举一个已选的字符串（即当前状态二进制位为1的位），再枚举一个未选的字符串（当前状态二进制位为0的位），通过这两个字符串的拼接来更新拼接之后新的状态，因为加进了一个没在状态中的字符串，所以状态变成了i|(1<<k) 假设i是当前枚举的状态，k是二进制位为0的位
所以状态转移就为
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+len[j][k]);
如果大家仔细观察一下代码中的关键转移部分，会发现：当我们要去更新dp[i|(1<<k)][k]状态时，dp[i][j]肯定已经是求好了的，在这道题目里dp[i][j]就是dp[i|(1<<k)][k]的子结构，每次都尝试着用dp[i|(1<<k)][k]的子结构去更新它
更多状态压缩的题目
http://blog.csdn.net/accry/article/details/6607703
[cpp]
#include<stdio.h>
#include<string.h>
#define max(a,b)(a>b?a:b)
int dp[1<<10+5][11];
int len[11][11];
int n;
char str[11][11];
int main()
{
int n,i,j,k,x,count;
int len1,len2,max;
while(scanf("%d",&n),n)
{
memset(len,0,sizeof(len));
for(i=0;i<n;i++)
scanf("%s",str[i]);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i!=j)
{
max=-1;//pay attention
len1=strlen(str[i]);
len2=strlen(str[j]);
for(k=0;k<len1;k++)
{
count=0;
for(x=0;x<len2&&(x+k)<len1;x++)
{
if(str[i][x+k]==str[j][x]) count++;
}
if(count>max) max=count;
}
if(max>len[i][j])
len[i][j]=len[j][i]=max;
}
}
}
memset(dp,0,sizeof(dp));
for(i=0;i<(1<<n);i++)
for(j=0;j<n;j++)
{
if(i&(1<<j))//if j is in the set of i
{
for(k=0;k<n;k++)
{
if(!(i&(1<<k)))//if k is not int the set of i,then process dp
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+len[j][k]);
}
}
}
max=-1;
for(i=0;i<(1<<n);i++)
for(j=0;j<n;j++)
if(dp[i][j]>max)
max=dp[i][j];
printf("%d/n",max);
}
return 0;
}
B题
http://poj.org/problem?id=1745
Dp[i][j]代表前i个数能否组成j，那么只要前i-1个数能组成j-a[i]或j+a[i]就可以了，注意j-a[i]<0时要取余，详见代码
dp[i][j]=dp[i-1][j-a[i]] || dp[i-1][j+a[i]];
[cpp]
把取余神马的都提前处理掉，可以加快速度
（bool）dp[i][j]=dp[i-1][j-a[i]]||dp[i-1][j+a[i]]
#include<stdio.h>
#include<string.h>
int a[10001];
bool dp[10001][101];
int n,m;
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
while(a[i]<0) a[i]+=m;
a[i]=a[i]%m;
}
dp[1][a[1]]=true;
for(i=2;i<=n;i++)
{
for(j=0;j<m;j++)
{
int t1=j-a[i];
while(t1<0) t1+=m;
int t2=j+a[i];
dp[i][j]=dp[i-1][t1]||dp[i-1][t2%m];
}
}
if(dp[n][0])
printf("Divisible/n");
else printf("Not divisible/n");
return 0;
}
C题
http://poj.org/problem?id=2955
经典的区间DP
Dp[i][j]代表i->j区间内最多的合法括号数
转移过程
dp[i][j]>?=dp[i][k]+dp[k+1][j];
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
[cpp]
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int dp[110][101];
char s[110];
int main()
{
char s[110];
int i,j,k;
while(scanf("%s",s)!=EOF)
{
int ans=0;
if(strcmp(s,"end")==0) break;
int len=strlen(s);
memset(dp,0,sizeof(dp));
for(k=0;k<len;k++)
{
for(i=0,j=k;j<len;i++,j++)
{
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
for(int t=i;t<j;t++)
dp[i][j]=max(dp[i][j],dp[i][t]+dp[t+1][j]);
}
}
printf("%d/n",dp[0][len-1]);
}
return 0;
}
D题
http://poj.org/problem?id=2537
Dp[i][j]代表前i个数最后一个是j时，总共的tights的数量，以为前后两个字符串的绝对值差不能超过1，那么转移过程显而易见
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
在这个方程里[i-1]这一维的数都是已经求好的最优子结构
[cpp]
#include<stdio.h>
#include<string.h>
double dp[110][15];
int main()
{
int k,n;
int i,j;
while(scanf("%d%d",&k,&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=k+1;i++)
dp[1][i]=1;
for(i=2;i<=n;i++)
for(j=1;j<=k+1;j++)
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
double ans=0;
for(i=1;i<=k+1;i++)
ans+=dp[n][i];
for(i=1;i<=n;i++)
ans/=(k+1);
ans*=100;
printf("%.5lf/n",ans);
}
return 0;
}
E:
http://poj.org/problem?id=3018
DAG上最长路
给出很多个盒子的大小，将小的盒子放入大的盒子，再将大的盒子放入更大的盒子，如此下去问你最多能有多少个盒子嵌套在一起
典型的DAG上最长路问题
DAG(DirectedAcyclic Graph)有向无环图，因为一个盒子能放进另一个盒子，另一个盒子肯定就放不进这个盒子，所以关系是单向的，也就是说形成的图是有向的，而且肯定不会有环。
状态
dp[i]表示到达i这个点所经过的最长路，那么可以用这个状态尝试着去更新i可以到达的点j
dp[j]=max(dp[j],dp[i]+1);
最后的答案就是dp[i]的最大值
还有一种写法是dfs搜一条最长路，具体见代码
[cpp]
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf = 100000000;
int box[510][1010];
int map[510][510];
int n,d;
bool ok;
int count=0;
bool solve(int a,int b)
{
int i,j;
bool flag=true;
for(i=1;i<=d;i++)
{
if(box[a][i]>=box[b][i])
{
flag=false;
break;
}
}
return flag;
}
void init()
{
int i,j;
memset(map,0,sizeof(map));
for(i=2;i<=n;i++)
{
if(solve(1,i))
{
map[1][i]=1;
ok=true;
}
}
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(solve(i,j))
{
map[i][j]=1;
}
}
}
}
int dp[510];
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&d)!=EOF)
{
n++;
ok=false;
for(i=1;i<=n;i++)
{
for(j=1;j<=d;j++)
{
scanf("%d",&box[i][j]);
}sort(box[i]+1,box[i]+1+d);
}
init();
if(!ok)
{
printf("Please look for another gift shop!");
continue;
}
dp[1]=0;
for(i=2;i<=n;i++)
dp[i]=-1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j]&&dp[i]!=-1)
{
if(dp[i]+1>dp[j])
{
dp[j]=dp[i]+1;
}
}
}
}
int ans=0;
for(i=1;i<=n;i++)
{
if(dp[i]>ans)
ans=dp[i];
}
printf("%d/n",ans);
}
return 0;
}
[cpp]
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf = 100000000;
int box[510][1010];
int map[510][510];
int n,d;
bool ok;
int count=0;
bool solve(int a,int b)
{
int i,j;
bool flag=true;
for(i=1;i<=d;i++)
{
if(box[a][i]>=box[b][i])
{
flag=false;
break;
}
}
return flag;
}
void init()
{
int i,j;
memset(map,0,sizeof(map));
for(i=2;i<=n;i++)
{
if(solve(1,i))
{
map[1][i]=1;
ok=true;
}
}
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(solve(i,j))
{
map[i][j]=1;
}
}
}
}
int ans;
void dfs(int p,int max)
{
if(max>ans) ans=max;
int i;
for(i=2;i<=n;i++)
{
if(map[p][i])
{
max++;
dfs(i,max);
max--;
}
}
}
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&d)!=EOF)
{
n++;
ok=false;
for(i=1;i<=n;i++)
{
for(j=1;j<=d;j++)
{
scanf("%d",&box[i][j]);
}sort(box[i]+1,box[i]+1+d);
}
init();
if(!ok)
{
printf("Please look for another gift shop!");
continue;
}
ans=0;
dfs(1,0);
printf("%d/n",ans);
}
return 0;
}
F题：经典的入门题，大家都会了，就跳过
G
http://poj.org/problem?id=2385
总共有两棵苹果树，时不时的会掉下苹果来，你最多只能往返两棵苹果树W次，给你第i分钟在哪颗苹果树会掉苹果的信息，问你最多能拿到多少的苹果
题目给出一个时间，一个次数两个限制，那么我们描述状态的时候就应该把它们描述进去
dp[i][j]代表前i分钟，最多（注意是最多）已经往返了j次的时候收获到的最多的苹果的数量，那么状态转移就很简单了，利用j的奇偶性我们可以判断出当前在那棵苹果树
记住！！！每次都有两种决策，要么停留在当前苹果树，要么离开当前苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j]+(j%2+1==num[i]));
//停留在i-1时刻的苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2==num[i]))
//换一棵苹果树
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2+1==num[i]));
//也可以不换苹果树
[cpp]
#include<cstdio>
#include<cstring>
int dp[1010][35];
int num[1010];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int T,W,i,j;
while(scanf("%d%d",&T,&W)!=EOF){
for(i=1;i<=T;i++) scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
if(num[1]==1) dp[1][0]=1;
dp[1][1]=1;
for(i=2;i<=T;i++){
for(j=0;j<=W;j++){
if(j==0) {
dp[i][j]=dp[i-1][j]+num[i]%2;
continue;
}
dp[i][j]=max(dp[i][j],dp[i-1][j]+(j%2+1==num[i]));
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2==num[i]));
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(j%2+1==num[i]));
}
}
printf("%d/n",dp[T][W]);
}
}
H
http://poj.org/problem?id=1976
dp[i][j]表示前i节车厢用j个火车头去拉所能拉的最大乘客量
转移过程很简单，尝试着自己推一下，具体见代码，看看能不能看懂是怎么转移的
[cpp]
#include<stdio.h>
#include<string.h>
int dp[55555][4],a[55555];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int t,i,j,k,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
a[0]=0;
for(i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1];
scanf("%d",&m);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=1;j<4;j++)
{
k=i-m;
if(k<0) k=0;
dp[i][j]=max(dp[i-1][j],dp[k][j-1]+a[i]-a[k]);
}
printf("%d/n",dp[n][3]);
}
return 0;
}
I,J 两题都是一类最简单的树形DP，依赖关系形成了一棵树，选择父节点就一定不能选择子节点
DP过程
注意：对于每个矛盾关系，从老板向员工连一条边
dp[i][0]表示不取i的最大值，可以由两个状态转移而来dp[i][0]+=sigma[max（dp[j][0],dp[j][1]）],j为儿子，即儿子取或不取都可以
dp[i][1]表示取i的最大值，初始值赋为1，那么儿子节点就不能取了，所以dp[i][1]=sigma(dp[j][0]);
判断方案是否唯一
观察状态转移的过程可知：dp[i][0]是由dp[j][0],dp[j][1]两个状态过来的，所以当dp[j][0]==dp[j][1]时，方案不唯一，即子节点选与不选都可以
但是注意前提是dp[i][0]更优与dp[i][1]，即i这个节点肯定被选择了，否则状态就仅仅由dp[j][1]转移而来，不能判断不唯一。
[cpp]
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;
#define max(a,b) a>b?a:b
const int maxn = 201;
vector<int> edge[maxn];
int dp[210][2];
void dfs(int u,int p)
{
int i,j;
dp[u][1]=1;
dp[u][0]=0;
for(i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(v==p) continue;
dfs(v,u);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][0],dp[v][1]);
}
}
int main(){
map<string,int> mm;
int n,i,tot;
char bos[110],a[110],b[110];
while(scanf("%d",&n),n)
{
tot=0;
for(i=0;i<=200;i++) edge[i].clear();
mm.clear();
scanf("%s",bos);mm[bos]=tot++;
for(i=0;i<n-1;i++)
{
scanf("%s%s",a,b);
if(mm.find(a)==mm.end()) mm[a]=tot++;
if(mm.find(b)==mm.end()) mm[b]=tot++;
edge[mm[b]].push_back(mm[a]);
}
dfs(0,0);bool flag=true;
for(i=0;i<n;i++)
{
flag=true;
if(dp[i][0]>dp[i][1])
{
for(int j=0;j<edge[i].size();j++)
{
if(dp[edge[i][j]][0]==dp[edge[i][j]][1])
{
flag=false;
break;
}
}
}
if(!flag) break;
}
printf("%d",max(dp[0][0],dp[0][1]));
if(dp[0][0]==dp[0][1]||!flag) printf(" No/n");
else printf(" Yes/n");
}
return 0;
}
作者：haha593572013
