{dp入门}

之前一直比较恐惧dp的题，暑假之前好好从头补一下。

数字三角形

dp[i][j]表示到第i层第j个房间时累计收集到的最大值，从上到下记忆化搜索即可

状态转移：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j];

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 int n;
 6 int m[110][110];
 7 int dp[110][110];
 8 int main()
 9 {
10     while(scanf("%d",&n)!=EOF)
11     {
12         memset(m,0,sizeof(m));
13         memset(dp,0,sizeof(dp));
14         int ans=0;
15         for(int i=1;i<=n;i++)
16             for(int j=1;j<=i;j++)
17                 scanf("%d",&m[i][j]);
18         for(int i=1;i<=n;i++)
19             for(int j=1;j<=i;j++)
20                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j];
21         for(int i=1;i<=n;i++)
22             ans=max(ans,dp[n][i]);
23         printf("%d
",ans);
24     }
25 }

View Code

题目链接：HihoCoder - 1038

01背包

dp[j]=max(dp[j-c[i]]+v[i],dp[j]);

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int maxn=520;
 6 int n,m;
 7 int dp[100110];
 8 int c[maxn],v[maxn];
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     for(int i=0;i<n;i++)
13         scanf("%d%d",&c[i],&v[i]);
14     for(int i=0;i<n;i++)
15         for(int j=m;j>=c[i];j--)
16             dp[j]=max(dp[j-c[i]]+v[i],dp[j]);
17     printf("%d
",dp[m]);
18 }

View Code

题目链接：HihoCoder - 1043

完全背包

和01背包相比只是j的顺序变了

本质是为了01背包只能选一件，完全背包可以多选

即01背包时的dp[ j-c[i] ]是上一次遍历时求出的，而完全背包用的则是本次遍历求出的值

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int maxn=520;
 6 int n,m;
 7 int dp[100110];
 8 int c[maxn],v[maxn];
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     for(int i=0;i<n;i++)
13         scanf("%d%d",&c[i],&v[i]);
14     for(int i=0;i<n;i++)
15         for(int j=c[i];j<=m;j++)
16             dp[j]=max(dp[j-c[i]]+v[i],dp[j]);
17     printf("%d
",dp[m]);
18 }

View Code

题目链接：https://nanti.jisuanke.com/t/20

如果之前的位置可以到达当前位置，更新最小值

if(j+x[j]>=i) dp[i]=min(dp[i],dp[j]+1); （j<i）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=110;
 7 int dp[maxn],x[maxn];
 8 int n;
 9 int main()
10 {
11     while(scanf("%d",&n)!=EOF)
12     {
13         memset(dp,0x3f,sizeof(dp));
14         dp[0]=0;
15         for(int i=0;i<n;i++)
16         {
17             scanf("%d",&x[i]);
18             for(int j=0;j<i;j++)
19             {
20                 if(j+x[j]>=i)
21                     dp[i]=min(dp[i],dp[j]+1);
22             }
23         }
24         printf("%d
",dp[n-1]);
25     }
26 }

View Code

题目链接：https://nanti.jisuanke.com/t/28

背包变形了一下，竟然又不会。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int n,m;
 7 long long dp[1010];
 8 int main()
 9 {
10     scanf("%d",&n);
11     m=(1+n)*n;
12     if(m%4)
13     {
14         puts("0");
15         return 0;
16     }
17     m/=4;
18     dp[0]=1;
19     for(int i=1;i<=n;i++)
20         for(int j=m;j>=i;j--)
21             dp[j]+=dp[j-i];
22     printf("%lld
",dp[m]/2);
23 
24 }

View Code

题目链接：HihoCoder - 1055

树dp，，转换成树上的背包？？

dp[u][j]以u为根涂j个桶的最大值。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 const int maxn=110;
 6 struct Edge
 7 {
 8     int v;
 9     int nex;
10 }e[maxn<<1];
11 int head[maxn];
12 int cnt=0;
13 int dp[maxn][maxn];
14 void add(int u,int v)
15 {
16     e[cnt].v=v;
17     e[cnt].nex=head[u];
18     head[u]=cnt++;
19 }
20 int n,m;
21 void dfs(int u,int pre)
22 {
23     for(int i=head[u];i!=-1;i=e[i].nex)
24     {
25         int v=e[i].v;
26         if(v==pre) continue;
27         dfs(v,u);
28         for(int j=m;j>=2;j--)
29             for(int k=1;k<j;k++)
30             dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
31     }
32 
33 }
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     memset(head,-1,sizeof(head));
38     cnt=0;
39     for(int i=1;i<=n;i++)
40         scanf("%d",&dp[i][1]);
41     for(int i=1;i<n;i++)
42     {
43         int u,v;
44         scanf("%d%d",&u,&v);
45         add(u,v);
46         add(v,u);
47     }
48     dfs(1,0);
49     printf("%d
",dp[1][m]);
50 }

View Code