DP总结
常规DP
[USACO1.5] [IOI1994]数字三角形 Number Triangles
解题思路
对于到达（i，j）点时的最大值，其状态仅由（i-1,j）和（i-1,j-1）决定。
故设计dp[ i ] [ j ] = MAX(dp[ i-1 ] [ j ],dp[ i-1 ] [ j-1 ])+num[ i ] [ j ]
#include<bits/stdc++.h>
using namespace std ;
int n ;
int num[1001][1001] ;
int dp[1001][1001] ;
int main()
{
scanf("%d",&n) ;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
scanf("%d",&num[i][j]) ;
memset(dp,0,sizeof(dp)) ;
dp[1][1]=num[1][1] ;
for(int i=1;i<=n-1;++i)
{
for(int j=1;j<=i;++j)
{
if(i+1<=n&&j<=i+1)
dp[i+1][j]=max(dp[i+1][j],dp[i][j]+num[i+1][j]) ;
if(i+1<=n&&j+1<=i+1)
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+num[i+1][j+1]) ;
}
}
int ans = 0 ;
for(int j=1;j<=n;++j) ans = max(ans,dp[n][j]) ;
printf("%d",ans) ;
return 0 ;
}
[NOIP1996 提高组] 挖地雷
解题思路
该题为比较简单的图上DP，注意题目要求只能从编号小的地窖走向编号较大的地窖。
设计dp[i]表示从i开始往下走能获得的最大价值。
考虑从编号最大的地窖开始倒着处理，由于题目要求输出路径，在更新DP时记录路径 即可
#include<bits/stdc++.h>
using namespace std ;
int mp[21][21],num[21],dp[21],nxt[21] ;
int n ;
int maxid , maxans=-1 ;
int main()
{
scanf("%d",&n) ;
for(int i=1;i<=n;++i) scanf("%d",&num[i]) ;
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j)
scanf("%d",&mp[i][j]) ;
memset(nxt,-1,sizeof(nxt)) ;
memset(dp,0,sizeof(dp)) ;
dp[n] = num[n] ;
for(int i=n-1;i>=1;--i)
{
dp[i]=num[i] ;
for(int j=i+1;j<=n;++j)
{
if(mp[i][j]==0) continue ;
if(dp[j]+num[i]>dp[i])
{
dp[i]=dp[j]+num[i] ;
nxt[i]=j ;
}
}
}
for(int i=1;i<=n;++i)
{
if(dp[i]>maxans)
{
maxans=dp[i] ;
maxid = i ;
}
}
for(;;)
{
printf("%d ",maxid) ;
maxid = nxt[maxid] ;
if(maxid==-1) break ;
}
printf("\n") ;
printf("%d",maxans) ;
return 0 ;
}
背包问题
0-1背包
[NOIP2005 普及组] 采药
解题思路
这是最典型的0-1背包问题，背包容量+物品价值，每个物品只能用一次。
设计dp[i]表示花费i时间所能获得的最大值。
考虑一次处理每一个物品，保证每一个物品只能用一次
然后在枚举花费时间时，当i<j时，dp[i]会影响到dp[j]，正正着枚举会导致同一个物品多次放入，所以应该倒着枚举。
#include<bits/stdc++.h>
using namespace std ;
int T,m ;
int value[101],tim[101] ;
int dp[1001] ;
int main()
{
scanf("%d%d",&T,&m) ;
for(int i=1;i<=m;++i)
scanf("%d%d",&tim[i],&value[i]) ;
memset(dp,0,sizeof(dp)) ;
for(int j=1;j<=m;++j)
for(int i=T;i>=0;--i)
if(i-tim[j]>=0)
dp[i]=max(dp[i],dp[i-tim[j]]+value[j]) ;
printf("%d",dp[T]) ;
return 0 ;
}