状态转移方程
- 递归关系 (从已知求得未知的表达式)
背包dp
-
0-1
背包,多重,完全,混合 -
模版套用
//多重背包
#include<bits/stdc++.h>
using namespace std;
const int N=507,M=1e5+7;
int p,n,x,y,z,dp[10005];
int main(){
cin>>p>>n;
for(int i=1;i<=n;i++){
scanf("%d %d %d",&x,&y,&z);
int t=1;
while(t<=x){
for(int j=p;j>=y*t;j--)dp[j]=max(dp[j],dp[j-y*t]+z*t);
x-=t;
t*=2;
}
if(x){
for(int j=p;j>=y*x;j--)dp[j]=max(dp[j],dp[j-y*x]+z*x);
}
}
printf("%d",dp[p]);
return 0;
}
区间dp,线性dp
-
令状态
f(i,j)
表示i
到j
所有元素合并能获得的价值的最大值 -
f(i,j)=max(f(i,k)+f(k+1,j)+cost)
树形dp
-
在树上进行dp
-
待办:树
单调队列优化
-
比你小还比你强()
-
RMQ
操作(区间最大/小值)
注意数组大小
-
dp[505][505]
--->RE
-
dp[5005][5005]
--->MLE