code1043 方格取数

开发者春志技术 2022年11月14日

0 收藏 352 点赞 5,068 浏览 1070 个字

第一次走用dfs枚举每种情况，第二次走用dp求剩下的最大值

设一个点集q用来保存有价值的点，排序，在最后加一个终点：x=m+1，y=m+1，v=0 //m是矩阵长宽

因为v=0的点是没有意义的，所以忽略它们，用q进行dfs

设当前点在q中的下标为p，已经积累的分数为score：

for(int i=p+;i<=n+;i++){
    if(q[i].y>=q[p].y){//可以到达
        a[q[i].x][q[i].y]=;
        dfs(i,score+q[i].v);
        a[q[i].x][q[i].y]=q[i].v;
    }
}

当p=n+1时，到了终点（n是有价值点的个数，n+1为最后添加的终点）

在残缺的a中dp找到第二次的最大价值，更新ans即可

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;struct Point{
    int x,y;
    int v;
}q[];
bool cnt(Point c,Point d){
    return c.x<d.x || (c.x==d.x && c.y<d.y);
}
int n,m;//m是边长，n是有值的点的个数
int a[][];
int d[][];
int ans=; int dp(){
    for(int i=;i<=m;i++){
        for(int j=;j<=m;j++){
            d[i][j]=max(d[i-][j],d[i][j-])+a[i][j];
        }
    }
    return d[m][m];
}void dfs(int p,int score){
    if(p==n+){
        int c=dp();
        if(ans<c+score)ans=c+score;
        return;
    }
    for(int i=p+;i<=n+;i++){
        if(q[i].y>=q[p].y){//可以到达
            a[q[i].x][q[i].y]=;
            dfs(i,score+q[i].v);
            a[q[i].x][q[i].y]=q[i].v;
        }
    }
}int main(){
    cin>>m;
    for(n=;true;n++){
        cin>>q[n].x>>q[n].y>>q[n].v;
        if(q[n].x==){n--;break;}
        a[q[n].x][q[n].y]=q[n].v;
    }
    sort(q+,q+n+,cnt);
    q[n+].x=m+;q[n+].y=m+;q[n+].v=;//终点
    dfs(,);
    cout<<ans<<endl;    return ;
}