【动态规划】洛谷2019 OI春令营

【P1464 Function】

【题解】

　　按照题目意思进行递归即可，但是过程中需要用到记忆化搜索。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll dp[50][50][50];
 5 ll w(ll a,ll b,ll c){
 6     if(a<=0||b<=0||c<=0){return 1;}
 7     if(a>20||b>20||c>20){return w(20,20,20);}
 8     if(a<b&&b<c){
 9         if(dp[a][b][c-1]==0) dp[a][b][c-1]=w(a,b,c-1);
10         if(dp[a][b-1][c-1]==0) dp[a][b-1][c-1]=w(a,b-1,c-1);
11         if(dp[a][b-1][c]==0) dp[a][b-1][c]=w(a,b-1,c);
12         return dp[a][b][c]=dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c];
13     }else{
14         if(dp[a-1][b][c]==0)dp[a-1][b][c]=w(a-1,b,c);
15         if(dp[a-1][b-1][c]==0)dp[a-1][b-1][c]=w(a-1,b-1,c);
16         if(dp[a-1][b][c-1]==0)dp[a-1][b][c-1]=w(a-1,b,c-1);
17         if(dp[a-1][b-1][c-1]==0)dp[a-1][b-1][c-1]=w(a-1,b-1,c-1);
18         return dp[a][b][c]
19         =dp[a-1][b][c]
20         +dp[a-1][b-1][c]
21         +dp[a-1][b][c-1]
22         -dp[a-1][b-1][c-1];
23     }
24 }
25 int main()
26 {
27     ll a,b,c;
28     while(~scanf("%lld%lld%lld",&a,&b,&c)){
29         if(a==-1&&b==-1&&c==-1){
30             break;
31         }
32         ll ans=w(a,b,c);
33         printf("w(%lld, %lld, %lld) = %lld
",a,b,c,ans);
34     }
35     return 0;
36 }

View Code

【P1002 过河卒】

【题解】

　　其实就是马的位置和马口的位置方案为0，无法转移，其他情况照常即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 30 ;
 5 ll dp[N][N];
 6 int dir[9][2] = {
 7         {-2,-1} , {-2,1},
 8     {-1,-2},        {-1,2},
 9              {0,0},
10     {1,-2},         {1,2},
11         {2,-1},   {2,1}
12 };
13 int main()
14 {
15     int n,m,x,y;
16     cin >> n >> m >> x >> y ;
17     n ++ , m ++ , x ++ , y ++ ;
18     dp[1][1] = 1 ;
19     for(int i=1;i<=n;i++){
20         for(int j=1;j<=m;j++){
21             if( i == 1 && j == 1 ) continue ;
22             bool f = true;
23             for(int k=0;k<9;k++){
24                 if( i == x + dir[k][0] && j == y + dir[k][1] )
25                     f = false ;
26             }
27             if( f )
28                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
29         }
30     }
31 
32     printf("%lld
",dp[n][m]);
33     return 0;
34 
35 }

View Code

【P1004 方格取数】

【题解】

这个题目和传纸条一样，开4维，分别枚举两个人在两个维度上同时跑动获取最大值的情况综合即可，

这个题目比传纸条更简单的是一个点可以经过两次并且确保两个维度的曼哈顿距离相同。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 12 ;
 4 int G[N][N],n,u,v,w;
 5 int dp[N][N][N][N];
 6 int main()
 7 {
 8     ios_base :: sync_with_stdio(false);
 9     cin.tie(NULL),cout.tie(NULL);
10 
11     cin >> n ;
12 
13     while ( cin >> u >> v >> w , (u+v+w) ){
14         G[u][v] = w ;
15     }
16 
17     for(int x1=1;x1<=n;x1++){
18         for(int y1=1;y1<=n;y1++){
19             for(int x2=1;x2<=n;x2++){
20                 for(int y2=1;y2<=n;y2++){
21 
22 
23                     if( !( x1 == n && y1 == n ) && ( x1 + y1 != x2 + y2 ) )
24                         continue ;
25 
26                     int tmp = 0 ;
27                     /*if( ( !(x1 == x2 && y1 == y2) ) ||
28                         ( (x1 == x2 && y1 == y2) && (x1 == n && y1 == n) ) ){
29                     */
30                         tmp = max( tmp , dp[x1-1][y1][x2-1][y2] );
31                         tmp = max( tmp , dp[x1-1][y1][x2][y2-1] );
32                         tmp = max( tmp , dp[x1][y1-1][x2-1][y2] );
33                         tmp = max( tmp , dp[x1][y1-1][x2][y2-1] );
34 
35                         dp[x1][y1][x2][y2] = tmp + G[x1][y1] + G[x2][y2] ;
36                         if( x1 == x2 && y1 == y2 ){
37                             dp[x1][y1][x2][y2] = dp[x1][y1][x2][y2] - G[x1][y1];
38                         }
39                     //}
40                 }
41             }
42         }
43     }
44     cout << dp[n][n][n][n] << endl;
45     return 0;
46 }

View Code

【P1006 传纸条】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 51;
 4 int dp[N][N][N][N],G[N][N];
 5 int n,m;
 6 int main()
 7 {
 8     ios_base :: sync_with_stdio(false);
 9     cin.tie(NULL) , cout.tie(NULL);
10     cin >> n >> m ;
11     for(int i=1;i<=n;i++)
12         for(int j=1;j<=m;j++)
13             cin >> G[i][j] ;
14     for(int x1=1;x1<=n;x1++){
15         for(int y1=1;y1<=m;y1++){
16             for(int x2=1;x2<=n;x2++){
17                 for(int y2=1;y2<=m;y2++){
18                     //如果没有达到终点,那么左下角是(x1,y1)，右上角就是(x2,y2)
19                     
20                     //这句话就是，如果过程中出现 步数不相符的情况，也就是说两者同时跑。不出现一个走10步，另一个走1步
21                     //if( !( x1 == n && y1 == m ) && ( x1 < x2 && y1 < y2 ) )
22                     if( !( x1 == n && y1 == m ) && ( x1 + y1 != x2 + y2 ) )
23                         continue ;
24                     
25                     //　更新的时候,过程中　不能存在两者都在同一个点的情况。
26                     if( ( x1 == n && y1 == m && x1==x2 && y1==y2 )
27                         || !( x1 == x2 && y1 == y2) ){
28                         int tmp = 0 ;
29                         tmp = max ( tmp , dp[x1-1][y1][x2-1][y2] );
30                         tmp = max ( tmp , dp[x1-1][y1][x2][y2-1] );
31                         tmp = max ( tmp , dp[x1][y1-1][x2-1][y2] );
32                         tmp = max ( tmp , dp[x1][y1-1][x2][y2-1] );
33 
34                         dp[x1][y1][x2][y2] = tmp + G[x1][y1] + G[x2][y2] ;
35                     }
36                 }
37             }
38         }
39     }
40 
41     cout << dp[n][m][n][m] << endl;
42     return 0;
43 }

View Code

【P1005 矩阵取数游戏】

【题意】

　　每一行拿m次，然后再拿n行，每一行的拿法都一样，拿左右端次序和对应的价值乘积最大。

考虑区间dp。

f[L][R]，在取L,R这一段之前两端取得的最大值

　　f[L][R] = max{ f[L-1][R] +a[L] * 2 ^(m+L-R-1) , f[L][R+1] + a[R] * 2^(m+L-R-1) }

最后还需要对于每一个单独的f[i][i]拿一遍，因为状态转移没有考虑长度为1的情况。

过程中还需要用到高精度，

高精度需要：

1、高精度+高精度

2、高精度×低精度

3、max{ 高精度，高精度}

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int mod = 1e4 ; // 10000
  4 const int N = 85;
  5 
  6 
  7 typedef struct High_precision{
  8     int Len , p[N] ;
  9     High_precision() {
 10         Len = 0 ;
 11         memset( p , 0 , sizeof p) ;
 12     }
 13 
 14     void Print(){
 15         printf("%d",p[Len]);
 16         for(int i = Len-1 ; i >= 1 ;i--){
 17             printf("%04d",p[i]);
 18         }
 19         puts("");
 20     }
 21 }Hp;
 22 
 23 Hp operator + (const Hp& A , const Hp& B ){
 24     int Len = max( A.Len , B.Len );
 25     Hp C ;
 26     int Carry = 0 ;
 27     for(int i=1 ; i<=Len ; i++ ){
 28         C.p[i] = ( A.p[i] + B.p[i] + Carry ) ;
 29         Carry = (C.p[i]) / mod ;
 30         C.p[i] = C.p[i] % mod ;
 31     }
 32     C.Len = Len ;
 33     if( Carry ){
 34         C.p[++C.Len] = Carry ;
 35     }
 36     return C ;
 37 }
 38 
 39 Hp operator * (const Hp& A , const int B ){
 40     Hp C ;
 41     int Len = A.Len ;
 42     int Carry = 0 ;
 43     for(int i = 1 ; i <= Len ; i ++ ){
 44         C.p[i] = A.p[i] * B + Carry ;
 45         Carry = C.p[i] / mod ;
 46         C.p[i] = C.p[i] % mod ;
 47         //C.p[i] = ( A.p[i] * B + Carry ) % mod ;
 48         //Carry = ( A.p[i] * B + Carry ) / mod ;
 49     }
 50     C.Len = A.Len ;
 51     while( Carry > 0 ){
 52         C.p[++C.Len] = Carry % mod ; Carry = Carry / mod ;
 53     }
 54 
 55     return C ;
 56 }
 57 
 58 Hp Max( const Hp& A, const Hp& B ){
 59     int LA = A.Len , LB = B.Len ;
 60     if( A.Len > B.Len ) return A ;
 61     else if( B.Len > A.Len ) return B ;
 62     for(int i=A.Len ; i>=1;i--){
 63         if( A.p[i] > B.p[i] ) return A ;
 64         else if( B.p[i] > A.p[i] ) return B ;
 65     }
 66     return A ;
 67 }
 68 
 69 Hp f[N][N] , Base[N] ;
 70 int a[N] ;
 71 int n,m;
 72 
 73 void Init(){
 74     Base[0].p[1] = 1 ;
 75     Base[0].Len = 1 ;
 76     for(int i=1;i<=m+2;i++)
 77         Base[i] = Base[i-1] * 2 ;
 78 
 79 }
 80 
 81 int main()
 82 {
 83 
 84     scanf("%d%d",&n,&m);
 85     Hp Ans , tmp ;
 86 
 87     Init();
 88     //Base[20].Print();
 89 
 90     for(int i=1;i<=n;i++){
 91         for(int j=1;j<=m;j++){
 92             scanf("%d",&a[j]);
 93             f[j][j].p[1] = a[j] ;
 94             f[j][j].Len = 1 ;
 95             //f[j][j].Print();
 96             //tmp = Max ( tmp , f[j][j] );
 97         }
 98         memset( f , 0 , sizeof f );//别忘了
 99 
100         //cout << " ### " ; tmp.Print();
101         for( int L = 1 ; L <= m ; L++ ){
102             for( int R = m ; R >= L ; R-- ){
103                 f[L][R] = Max( f[L-1][R] + Base[m+L-R-1] * a[L-1] , f[L][R] );
104                 f[L][R] = Max( f[L][R+1] + Base[m+L-R-1] * a[R+1] , f[L][R] );
105             }
106         }
107         tmp.Len = 1 ;
108         tmp.p[1] = 0 ;
109         for( int j = 1 ; j <= m ;j++ ){
110             tmp = Max ( tmp , f[j][j] + Base[m] * a[j] ) ;
111         }
112 
113         //cout << " ### " ; tmp.Print();
114 
115         Ans = Ans + tmp ;
116     }
117 
118     Ans.Print();
119     return 0;
120 }
121 
122 /*
123 2 3
124 1 2 3
125 3 4 2
126 
127 */

View Code

【P1049 装箱问题】

【题解】01背包

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 25000 ;
 4 int dp[N];
 5 int main()
 6 {
 7     int V , n ;
 8     cin >> V >> n ;
 9 
10     for(int i=1,v;i<=n;i++){
11         scanf("%d",&v);
12         for(int j=V;j>=v;j--){
13             dp[j] = max(dp[j],dp[j-v]+v);
14         }
15     }
16     printf("%d
",V-dp[V]);
17     return 0;
18 }

View Code

【P1541 乌龟棋】

【感受】

　　当我做这个题目的时候不得不佩服当初杨宗耀是真NB，可能大家都想不出来的，他都能做出来，当初我觉得他写的四维DP也太难想到了吧，后来就想到了，而且做出来了。我真的佩服至今。

【题解】

　　考虑四个维度每一个维度都用了多少张牌，然后通过状态转移过来即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 355;
 5 const int M = 41;
 6 int dp[M][M][M][M],a[N];
 7 int n,m;
 8 int main(){
 9     scanf("%d%d",&n,&m);
10 
11     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
12 
13     dp[0][0][0][0] = a[1] ;
14     int cnt = 0 ;
15     int One = 0 , Two = 0 , Three = 0 , Four = 0 ;
16     for(int i=1,w;i<=m;i++){
17         scanf("%d",&w);
18         if( w == 1 ) One ++ ;
19         else if( w == 2 ) Two ++ ;
20         else if( w == 3 ) Three ++ ;
21         else if( w == 4 ) Four ++ ;
22     }
23     for(int o=0;o<=One;o++){
24         for(int t=0;t<=Two;t++){
25             for(int th=0;th<=Three;th++){
26                 for(int f=0;f<=Four ;f++){
27 
28                     int dis = 1+ o + t*2 + th*3 + f*4 ;
29                     if( f >= 1 ){
30                         dp[o][t][th][f] =
31                         max( dp[o][t][th][f-1] + a[dis]
32                         , dp[o][t][th][f] );
33                     }
34                     if( th >= 1 ){
35 
36                         dp[o][t][th][f] =
37                         max( dp[o][t][th-1][f] + a[dis]
38                         , dp[o][t][th][f]);
39                     }
40                     if( t >= 1 ){
41                         dp[o][t][th][f] =
42                         max( dp[o][t-1][th][f] + a[dis]
43                         , dp[o][t][th][f]);
44                     }
45                     if( o >= 1 ){
46                         dp[o][t][th][f] =
47                         max( dp[o-1][t][th][f] + a[dis]
48                         , dp[o][t][th][f]);
49                     }
50                 }
51             }
52         }
53     }
54     printf("%d
",dp[One][Two][Three][Four]);
55     return 0;
56 }

View Code

【P1048 采药】

【题解】

01背包模板题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e4+10;
 4 int dp[N];
 5 int main()
 6 {
 7     int V,n;
 8     cin >> V >> n ;
 9     for(int i=1,v,w;i<=n;i++){
10         cin >> v >> w ;
11         for(int j=V;j>=v;j--){
12             dp[j] = max( dp[j] , dp[j-v]+w);
13         }
14     }
15     cout << dp[V] << endl;
16     return 0;
17 }

View Code