动态规划训练第一阶段（for初学者）(一)

A WordStack
题目链接：http://poj.org/problem id=2817
一些二进制的基本知识
判断j是否属于集合i：i&(1< 在集合i中去除j：i-(1< 在集合i中加入点j：i|(1<
先预处理出len[i][j]表示第i个字符串与第j个字符串组合能匹配的最大字符数
用一个数的二进制来表示那些字符串，那些字符串还没有选，即二进制位为1的表示已经选了，为0的表示还没有选
Dp[i][j]代表当选取的字符串为i状态，且最后一个选取的字符串是第j个字符串时的最优值
状态转移：枚举某个状态时，枚举一个已选的字符串（即当前状态二进制位为1的位），再枚举一个未选的字符串（当前状态二进制位为0的位），通过这两个字符串的拼接来更新拼接之后新的状态，因为加进了一个没在状态中的字符串，所以状态变成了i|(1< 所以状态转移就为
dp[i|(1< 如果大家仔细观察一下代码中的关键转移部分，会发现：当我们要去更新dp[i|(1< 更多状态压缩的题目
http://blog.csdn.net/accry/article/details/6607703



[cpp]
#include
#include
#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 scanf("%s",str[i]);
for(i=0;i for(j=0;j if(i!=j)
{
max=-1;//pay attention
len1=strlen(str[i]);
len2=strlen(str[j]);
for(k=0;k {
count=0;
for(x=0;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< for(j=0;j {
if(i&(1< {
for(k=0;k {
if(!(i&(1< dp[i|(1< }
}
}
max=-1;
for(i=0;i<(1< for(j=0;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
#include
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 {
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
#include
#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