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
