DP--方格取数问题

方格取数

Description

　　设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
　　

　　某人从图中的左上角A出发，可以向下行走，也可以向右行走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
　　此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

Input

　　第一行为一个整数N（N≤10），表示N×N的方格图。
　　接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行“0 0 0”表示结束。

Output

　　第一个整数，表示两条路径上取得的最大的和。

Sample Input

2 3 13

2 6 6

3 5 7

4 4 14

5 2 21

5 6 4

6 3 15

7 2 14

0 0 0

Sample Output

基本思路：就是利用一个四维的数组；f[i][j][k][l],就表示为两条路经经过（i,j）和（k,l）的时候做大的和，两个点不能相同，如果相同了的话，就只能有一个值

状态表示：
f[i][j][k][l]为由两条不交叉的线路走到 (i, j)，(k, l) 位置时的最大和
它的上一步可能有四种情况：
第一个点由上走来，第二个点也由上走来，此时的好感度和为f[i - 1][j][k - 1][l]
第一个点由上走来，第二个点则由左走来，此时的好感度和为f[i - 1][j][k][l - 1]
第一个点由左走来，第二个点则由上走来，此时的好感度和为f[i][j - 1][k - 1][l]
第一个点由左走来，第二个点也由左走来，此时的好感度和为f[i][j - 1][k][l - 1]
取四种情况中的最大者加上两个点的权值即可。
特判：一直到终点之前，为了防止路径重叠，不能让两个点相同，所以最后如果两个点相同的话，减去一个点的权值即可。

#include <bits/stdc++.h>
using namespace std;
const int N=15,inf=0x3f3f3f;; 
int a[N][N],f[N][N][N][N],n,m,minn,maxn,x,y,z; 
inline int read()
{
    int x=0;char y='*',z=getchar();
    while(z<'0'||z>'9') y=z,z=getchar();
    while(z>='0'&&z<='9') x=(x<<3)+(x<<1)+(z-'0'),z=getchar();
    return y=='-'?-x:x;
}
int main()
{
    n=read();
    while(cin>>x>>y>>z){
        if((x+y+z)==0) break;
        a[x][y]=z;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int h=1;h<=n;h++)
                for(int k=1;k<=n;k++)
                {
                    int temp1=max(f[i-1][j][h-1][k],f[i][j-1][h][k-1]);
                    int temp2=max(f[i-1][j][h][k-1],f[i][j-1][h-1][k]);
                    f[i][j][h][k]=max(temp1,temp2)+a[i][j];
                    if(i!=h&&j!=k) f[i][j][h][k]+=a[h][k];
                }
    cout<<f[n][n][n][n]<<endl;
    return 0;
}

View Code

优化思路：

那么设f[i,j,k]表示走到了第i步，第一条路径向右走了j步，第二条路径向右走了k步。

那么一个N*N的矩阵我们从左上角走到右下角需要走2*N-2步（不算上起点1,1）

初始化：f[0][1][1]=a[1][1]; step+2=左+右

有一个问题就是现在已知走的步数以及向右走了几步；现在所在点的坐标怎么表示？

比如走了 i 步，此时向右走了 j 步，此时所在的坐标为（ i+2-j , j ）

f[i,j,k]=max{ f[i-1,j,k] ,f[i-1,j-1,k] ,f[i-1,j-1,k-1], f[i-1,j,k-1] } + (j==k ? a[i+2-j][j] : a[i+2-j][j]+a[i+2-k][k]);

#include <bits/stdc++.h>
using namespace std;
const int N=11;
int a[N][N];
int f[N<<1][N][N];
int main{
    int n;
    cin>>n;
    int x,y,z;
    while(cin>>x>>y>>z) { if(!x&&!y&&!z) break; a[x][y]=z;}
    f[0][1][1]=a[1][1];//要先赋初值 
    for(int k=1;k<=2*N-2;k++)
     for(int i1=1;i1<=min(k+1,N);i1++)
       for(int i2=1;i2<=min(k+1,N);i2++){
           int temp1=max(f[k-1][i1][i2],f[k-1][i1-1][i2]);
           int temp2=max(f[k-1][i1][i2-1],f[k-1][i1-1][i2-1]);
        f[k][i1][i2]=max(temp1,temp2);
        f[k][i1][i2]+=a[k+2-i1][i1]+a[k+2-i2][i2];
        if(i1==i2) f[k][i1][i2]-=a[k+2-i2][i2];//同一点只算一次     
    }
    cout<<f[2*N-2][N][N]<<endl;
    return 0;
}

那么根据状态表示！我们还可以进行空间优化：

在这里有个异或^ :相当于一只在换0 1 0^1=1;1^1=0;

//yrnddup c++ code
#include <bits/stdc++.h>
using namespace std;
const int N=11;
int a[N][N];
int f[2][N][N]; 
int main()
{
    int n;
    cin>>n;
    int x,y,z;
    while(cin>>x>>y>>z) { if(!x&&!y&&!z) break; a[x][y]=z;}
    f[0][1][1]=a[1][1];//要先赋初值 
    int now=0,pre=0;
    for(int k=1;k<=2*N-2;k++)
    {
        now=pre^1;
        for(int i1=1;i1<=min(k+1,N);i1++)
          for(int i2=1;i2<=min(k+1,N);i2++){
              int temp1=max(f[pre][i1][i2],f[pre][i1-1][i2]);
               int temp2=max(f[pre][i1][i2-1],f[pre][i1-1][i2-1]);
            f[now][i1][i2]=max(temp1,temp2);
            f[now][i1][i2]+=a[k+2-i1][i1]+a[k+2-i2][i2];
            if(i1==i2) f[now][i1][i2]-=a[k+2-i2][i2];//同一点只算一次     
       } 
       pre=now;
    }
    cout<<f[now][N][N]<<endl;
    return 0;
}

方格取数

Description

　　给定一个 N * M 的矩阵，记录左上角为 (1,1) ，右下角为 ( N , M ) ，现在从 (1,1)始取数，每次只能向下或向右移动一个单位，最终到达 ( N , M ) ，我们把路径上有的数相乘，记为 C 。使 C 的结果最大已经不能满足我们了，现在我们想让 C尾的零最少。
　　Ps. 11000 末尾有 3 个零， 100000100 末尾有 2 个零。

Input

　　第一行包含两个正整数 N ， M 表示矩阵大小。
　　接下来 N 行每行 M 个正整数给出整个矩阵。

Output

　　输出仅一行包含一个整数表示所求最小值。

Sample Input

3 3

1 2 3

10 5 100

10 8 9

Sample Output

思路简直奇妙：就是弄两个数组，分别求出到每个地方经过的最小的2和5的次数，最后最小的0就是2和5的一个最小值

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
long long f[N][N],a[N][N],b[N][N];
int n,m,tmp,num;
int main(){
    cin>>n>>m;
    int x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            tmp=x,num=0;
            while(tmp%2==0)
            {
                num++;tmp/=2;
            } 
            a[i][j]=num;
            tmp=x;num=0;
            while(tmp%5==0)
            {
                num++;tmp/=5;
            }
            b[i][j]=num;
        }
    for(int i=1;i<=n;i++) f[i][1]=a[i][1]+f[i-1][1];
    for(int i=1;i<=m;i++) f[1][i]=a[1][i]+f[1][i-1];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
    int ans1=f[n][m];//2的个数
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][1]=b[i][1]+f[i-1][1];
    for(int i=1;i<=m;i++) f[1][i]=b[1][i]+f[1][i-1];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            f[i][j]=min(f[i-1][j],f[i][j-1])+b[i][j];
    int ans2=f[n][m];
    //cout<<ans1<<endl<<ans2<<endl;
    cout<<min(ans1,ans2)<<endl;
    return 0;
}

View Code

传纸条(NOIP2008)

Description

　　小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
　　在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
　　还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

Input

　　输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1 < m,n <= 50）。
　　接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

Output

　　输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

Sample Input

3 3 0 3 9 2 8 5 5 7 0

Sample Output

其实就跟第一个一样，直接放代码了：

#include <bits/stdc++.h>
using namespace std;
const int N=55; 
int a[N][N],f[N][N][N][N]; //就是选两条路径 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int i,j,x1,x2,x3,x4;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(x1=1;x1<=n;x1++){
        for(x2=1;x2<=m;x2++){
            for(x3=1;x3<=n;x3++){
                for(x4=1;x4<=m;x4++){
                    f[x1][x2][x3][x4]=max(max(f[x1-1][x2][x3-1][x4],f[x1-1][x2][x3][x4-1]),max(f[x1][x2-1][x3-1][x4],f[x1][x2-1][x3][x4-1]))+a[x1][x2]+a[x3][x4];
                    if(x1==x3&&x2==x4)
                        f[x1][x2][x3][x4]-=a[x1][x2]; 
                }
            } 
        }
    }
    printf("%d",f[n][m][n][m]);
    return 0;
}

View Code

三取方格数

Description

【题目背景】
　　JerryZhou同学经常改编习题给自己做。
　　这天，他又改编了一题。。。。。
【问题描述】
　　设有N*N的方格图，我们将其中的某些方格填入正整数，
　　而其他的方格中放入0。
　　某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
　　在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
　　此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

Input

　　第一行:N (4<=N<=20)
　　接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0

Output

　　一行，表示最大的总和。

Sample Input

4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 2 4

Sample Output

思路：多进程DP；f[step][x1][x2][x3]表示当走到第step步时，三个点分别取x1,x2,x3时的最优解。

　　由于只能向下或向右移动，所以当移动步数一定时，所能移动到的格子是一个 / 的对角线，所以枚举三次移动到的横坐标，可以O(1)第算出纵坐标，注意每个方格只能取一次。

可以用f[x1][y1][x2][y2][x3][y3]表示现在三个人的状态（(x1,y1),(x2,y2),(x3,y3)分别是三人坐标）

考虑到三个人是同时走的，所以在每一步，x1+y1=x2+y2=x3+y3

所以可以用f[step][x1][x2][x3]表示三人的状态，step+2=x1+y1=x2+y2=x3+y3，可以算出y1,y2,y3

其实前面选择两条路经的时候要也可以这样做！！但是懒得写了咳咳

#include <bits/stdc++.h>
using namespace std;
const int N=25; 
int Map[N][N],f[N*2][N][N][N],n,m;  
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&Map[i][j]);
    f[1][1][1][1]=Map[1][1];//初始化
    for(int step=2;step<=2*n-1;step++)
        for(int x1=max(1,step-n+1);x1<=min(n,step);x1++)
             for(int x2=max(1,step-n+1);x2<=min(n,step);x2++)
                 for(int x3=max(1,step-n+1);x3<=min(n,step);x3++)
                 {
                     int tmp=Map[x1][step-x1+1]+Map[x2][step-x2+1]+Map[x3][step-x3+1];
                     if(x1==x2) tmp-=Map[x1][step-x1+1];
                    if(x1==x3) tmp-=Map[x1][step-x1+1];
                    if(x2==x3) tmp-=Map[x2][step-x2+1];
                    if(x1==x2&&x1==x3) tmp+=Map[x1][step-x1+1];//多减去了一次
                    f[step][x1][x2][x3]=max(f[step-1][x1][x2][x3],max(f[step-1][x1-1][x2][x3],max(f[step-1][x1][x2-1][x3],max(f[step-1][x1][x2][x3-1],max(f[step-1][x1-1][x2-1][x3],max(f[step-1][x1-1][x2][x3-1],max(f[step-1][x1][x2-1][x3-1],f[step-1][x1-1][x2-1][x3-1])))))))+tmp;
                }
                     
    cout<<f[2*n-1][n][n][n]<<endl;                 
    return 0;
}

View Code

其实还有网络流的做法，以后来补充吧