ACM板子——【动态规划问题】全收录

一、背包问题

【1.1】01背包

1 for(int i=1;i<=n;i++)
2     for(int j=m;j>=v[i];j--)
3         f[j]=max(f[j],f[j-v[i]]+w[i]);

【1.2】完全背包

1 for(int i=1;i<=n;i++)
2     for(int j=v[i];j<=m;j++)
3         f[j]=max(f[j],f[j-v[i]]+w[i]);

【1.3】多重背包问题1

1 for(int i=0;i)
2 {
3     int v,w,s;
4     cin>>v>>w>>s;
5     for(int j=m;j>=0;j--)
6         for(int k=1;k<=s&&k*v<=j;k++)
7             f[j]=max(f[j],f[j-k*v]+k*w);
8 }

【1.4】多重背包问题2（数据更大的情况下，二进制优化）

 1 #include
 2 #include
 3 #define endl '\n'
 4 #define ll long long
 5 using namespace std;
 6 const int N=3e4+10;
 7 int f[N],v[N],w[N];
 8 int main()
 9 {
10     int n,m;
11     cin>>n>>m;
12     int cnt=0;
13     for(int i=1;i<=n;i++)
14     {
15         int a,b,s;
16         cin>>a>>b>>s;
17         int k=1;
18         while(k<=s)
19         {
20             cnt++;
21             v[cnt]=a*k;
22             w[cnt]=b*k;
23             s-=k;
24             k*=2;
25         }
26         if(s>0)
27         {
28             cnt++;
29             v[cnt]=a*s;
30             w[cnt]=b*s;
31         }        
32     }
33     n=cnt;
34     for(int i=1;i<=n;i++)
35         for(int j=m;j>=v[i];j--)
36             f[j]=max(f[j],f[j-v[i]]+w[i]);
37     cout<endl;
38     return 0;    
39 }

【1.5】多重背包问题3（单调队列优化）

【1.6】混合背包问题

【1.7】二维费用背包问题

 1 #include
 2 using namespace std;
 3 const int N=110;
 4 int f[N][N];
 5 int main()
 6 {
 7     int n,v,m;
 8     cin>>n>>v>>m;
 9     for(int i=0;i)
10     {
11         int a,b,c;
12         cin>>a>>b>>c;
13         for(int j=v;j>=a;j--)
14             for(int k=m;k>=b;k--)
15                 f[j][k]=max(f[j][k],f[j-a][k-b]+c);
16     }
17     cout<<f[v][m];
18     return 0;
19 }

 【1.8】分组背包问题

 1 #include
 2 using namespace std;
 3 const int N=110;
 4 int f[N],v[N],w[N];
 5 int main()
 6 {
 7     int n,m;
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++)
10     {
11         int s;
12         cin>>s;
13         for(int j=1;j<=s;j++) cin>>v[j]>>w[j];
14         for(int j=m;j>=0;j--)
15             for(int k=1;k<=s;k++)
16                 if(j>=v[k])
17                     f[j]=max(f[j],f[j-v[k]]+w[k]);
18     }
19     cout<<f[m];
20     return 0;
21 }

二、线性DP

【2.1】数字金字塔

 1 #include
 2 using namespace std;
 3 const int N=510;
 4 int f[N][N],w[N][N];
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++)
10         for(int j=1;j<=i;j++)
11             cin>>w[i][j];
12     for(int i=n;i;i--)
13         for(int j=1;j<=i;j++)
14             f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
15     cout<1][1];
16 }

【2.3】最长上升子序列

 1 #include
 2 using namespace std;
 3 const int N=1e5+10;
 4 int a[N],f[N];
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++) cin>>a[i];
10     for(int i=1;i<=n;i++)
11     {
12         f[i]=1;
13         for(int j=1;j)
14             if(a[j]<a[i])
15                 f[i]=max(f[i],f[j]+1);
16     }
17     int ans=0;
18     for(int i=1;i<=n;i++) ans=max(ans,f[i]);
19     cout<endl;
20     return 0;
21 }

【2.4】最长上升子序列2