2023年8月1日发(作者：)

DP基础题型及解题思路总结DP基础题型及解题思路总结⼀、解题⼀般思路①、状态表⽰：(1)、集合：合法的所有⽅案的集合(2)、属性：Max/Min/Count②、状态计算—集合的划分：划分依据——最后⼀个不同的点⼆、01背包问题题⽬：有 N 件物品和⼀个容量是 V 的背包。每件物品只能使⽤⼀次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤。输出最⼤价值。输⼊格式第⼀⾏两个整数，N，V，⽤空格隔开，分别表⽰物品数量和背包容积。接下来有 N ⾏，每⾏两个整数 vi,wi，⽤空格隔开，分别表⽰第 i 件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值。数据范围0=v[i]的情况下才会考虑，代码如下：代码：#include#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxn=1e3+5;int N,V,v[maxn],w[maxn];int dp[maxn][maxn];//dp[i][j]

前i件物品中体积不超过j的最⼤价值int main(){ cin>>N>>V; for(int i=1;i<=N;i++) scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=N;i++) for(int j=1;j<=V;j++) { dp[i][j]=dp[i-1][j];//取不了要保持 if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); } cout<#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxn=1e3+5;int N,V,v,w;int dp[maxn];//dp[i]所拿物品体积不超过i的最⼤价值int main(){ cin>>N>>V; for(int i=1;i<=N;i++) { scanf("%d%d",&v,&w); for(int j=V;j>=v;j--)//从⼤到⼩ dp[j]=max(dp[j],dp[j-v]+w); } cout<

摘花⽣#include#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int N=105;int T,R,C;int mp[N][N];int dp[N][N];int main(){ cin>>T; while(T--) { memset(mp,0,sizeof(mp)); cin>>R>>C; for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) scanf("%d",&mp[i][j]); /* dp[1][1]=mp[1][1]; for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) if(i==1&&j==1) continue; else dp[i][j]=max(dp[i-1][j]+mp[i][j],dp[i][j-1]+mp[i][j]);*/ //上述dp过程的优化 for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]; cout<#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;int N;ll a[1005];int dp[1005];//dp[i]以a[i]结尾的⼦序列的最⼤值int main(){ cin>>N; for(int i=1;i<=N;i++) cin>>a[i]; for(int i=1;i<=N;i++) { dp[i]=1;//倒数第⼆个数不存在的情况 for(int j=1;ja[j]) dp[i]=max(dp[i],dp[j]+1);//a[i]是max(dp[1~i-1])+1 } } int ans=0; for(int i=1;i<=N;i++) ans=max(ans,dp[i]); cout<

2023年8月1日发(作者：)

DP基础题型及解题思路总结DP基础题型及解题思路总结⼀、解题⼀般思路①、状态表⽰：(1)、集合：合法的所有⽅案的集合(2)、属性：Max/Min/Count②、状态计算—集合的划分：划分依据——最后⼀个不同的点⼆、01背包问题题⽬：有 N 件物品和⼀个容量是 V 的背包。每件物品只能使⽤⼀次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤。输出最⼤价值。输⼊格式第⼀⾏两个整数，N，V，⽤空格隔开，分别表⽰物品数量和背包容积。接下来有 N ⾏，每⾏两个整数 vi,wi，⽤空格隔开，分别表⽰第 i 件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值。数据范围0=v[i]的情况下才会考虑，代码如下：代码：#include#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxn=1e3+5;int N,V,v[maxn],w[maxn];int dp[maxn][maxn];//dp[i][j]

前i件物品中体积不超过j的最⼤价值int main(){ cin>>N>>V; for(int i=1;i<=N;i++) scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=N;i++) for(int j=1;j<=V;j++) { dp[i][j]=dp[i-1][j];//取不了要保持 if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); } cout<#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxn=1e3+5;int N,V,v,w;int dp[maxn];//dp[i]所拿物品体积不超过i的最⼤价值int main(){ cin>>N>>V; for(int i=1;i<=N;i++) { scanf("%d%d",&v,&w); for(int j=V;j>=v;j--)//从⼤到⼩ dp[j]=max(dp[j],dp[j-v]+w); } cout<

摘花⽣#include#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;const int N=105;int T,R,C;int mp[N][N];int dp[N][N];int main(){ cin>>T; while(T--) { memset(mp,0,sizeof(mp)); cin>>R>>C; for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) scanf("%d",&mp[i][j]); /* dp[1][1]=mp[1][1]; for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) if(i==1&&j==1) continue; else dp[i][j]=max(dp[i-1][j]+mp[i][j],dp[i][j-1]+mp[i][j]);*/ //上述dp过程的优化 for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]; cout<#include#include#include#include#define ll long long#define inf 0x3f3f3f3fusing namespace std;int N;ll a[1005];int dp[1005];//dp[i]以a[i]结尾的⼦序列的最⼤值int main(){ cin>>N; for(int i=1;i<=N;i++) cin>>a[i]; for(int i=1;i<=N;i++) { dp[i]=1;//倒数第⼆个数不存在的情况 for(int j=1;ja[j]) dp[i]=max(dp[i],dp[j]+1);//a[i]是max(dp[1~i-1])+1 } } int ans=0; for(int i=1;i<=N;i++) ans=max(ans,dp[i]); cout<