| NOIP200003方格取数 |
| 难度级别： D； 编程语言：不限；运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
XYZ 是首师大附中信息技术团编程大神之一，尤其近两个月水平提升迅猛，一发不可收拾。老师说他前途不可估量，于是他有一点小骄傲，好像没有什么题能难住他。这让另一位编程高手 WJH 看不下去了，于是要求出一道题考考他，如果 10 分钟内做不出来，以后不许再这么“嚣张”，XYZ 欣然同意。WJH 要求 XYZ 帮助 ZYT 解决一个问题： |
|
输入
|
|
第一行为一个整数 N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
|
|
输出
|
|
只需输出一个整数，表示2条路径上取得的最大的和。
|
|
输入示例
|
|
8
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 |
|
输出示例
|
|
67
|
|
其他说明
|
|
数据范围：所有正整数都不会超过1000，太大了杨老师没那么多积分给的！
|
第一种方法是，我们可以使用费用流，对于每个点我们拆成两个点i,i`，并从i向i`连两条弧，容量均为1，一条费用为0，一条费用为-wi.
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=210; const int maxm=4010; const int INF=1000000000; struct ZKW { int n,m,s,t,first[maxn],next[maxm]; int ans,cost; int vis[maxn],inq[maxn],d[maxn]; struct Edge {int from,to,flow,cost;}edges[maxm]; void init(int n) { this->n=n;m=0; memset(first,-1,sizeof(first)); } void AddEdge(int from,int to,int cap,int cost) { edges[m]=(Edge){from,to,cap,cost};next[m]=first[from];first[from]=m++; edges[m]=(Edge){to,from,0,-cost};next[m]=first[to];first[to]=m++; } int BFS() { queue<int> Q; rep(i,1,n) d[i]=INF; d[t]=0;inq[t]=1;Q.push(t); while(!Q.empty()) { int x=Q.front();Q.pop();inq[x]=0; ren { Edge& e=edges[i^1]; if(e.flow&&d[e.from]>d[x]+e.cost) { d[e.from]=d[x]+e.cost; if(!inq[e.from]) inq[e.from]=1,Q.push(e.from); } } } rep(i,0,m-1) edges[i].cost+=d[edges[i].to]-d[edges[i].from]; cost+=d[s];return d[s]!=INF; } int DFS(int x,int a) { if(x==t||!a) {ans+=cost*a;return a;} int flow=0,f;vis[x]=1; ren { Edge& e=edges[i]; if(e.flow&&!e.cost&&!vis[e.to]&&(f=DFS(e.to,min(a,e.flow)))) { flow+=f;a-=f; e.flow-=f;edges[i^1].flow+=f; if(!a) break; } } return flow; } int solve(int s,int t) { ans=cost=0;this->s=s;this->t=t; while(BFS()) do memset(vis,0,sizeof(vis));while(DFS(s,INF)); return ans; } }sol; int n,w[15][15]; int id(int x,int y,int t) {return t*n*n+(x-1)*n+y;} int main() { n=read();sol.init(n*n*2); while(1) { int x=read(),y=read(),v=read(); if(!x) break; w[x][y]=v; } rep(i,1,n) rep(j,1,n) { sol.AddEdge(id(i,j,0),id(i,j,1),1,-w[i][j]); sol.AddEdge(id(i,j,0),id(i,j,1),1,0); if(i+1<=n) sol.AddEdge(id(i,j,1),id(i+1,j,0),1,0); if(j+1<=n) sol.AddEdge(id(i,j,1),id(i,j+1,0),1,0); } printf("%d ",-sol.solve(id(1,1,0),id(n,n,1))); return 0; }
第二种方法是，我们使用DP。考虑一个人走两遍相当于两个人同时走，设f[x1][y1][x2][y2]表示第一个人走到了(x1,y1)，第二个人走到了(x2,y2)最大收益。
转移时枚举上一次两个人在哪里，并加上这一步造成的收益：f[x1][y1][x2][y2]=Max(f[x1-1][y1][x2-1][y2],f[x1][y1-1][x2][y2-1],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2])+w[x1][y1]+(x1!=x2||y1!=y2)*w[x2][y2].时间复杂度为O(N^4)
注意因为同时走，x1+y1恒等于x2+y2，可以将时间复杂度优化为O(N^3).
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=15; int n,w[maxn][maxn],f[maxn][maxn][maxn]; int max(int a,int b,int c,int d) { return max(max(a,b),max(c,d)); } int dp(int x1,int y1,int x2) { if(x1==1&&y1==1) return w[1][1]; int y2=x1+y1-x2; if(x1<1||x2<1||x1>n||x2>n||y1<1||y2<1||y1>n||y2>n) return -1<<30; int& ans=f[x1][y1][x2]; if(ans>=0) return ans; int tmp=max(dp(x1-1,y1,x2-1),dp(x1,y1-1,x2-1),dp(x1,y1-1,x2),dp(x1-1,y1,x2)); return ans=tmp+w[x1][y1]+(x1==x2?0:1)*w[x2][y2]; } int main() { memset(f,-1,sizeof(f)); n=read(); while(1) { int x=read(),y=read(),v=read(); if(!x) break; w[x][y]=v; } printf("%d ",dp(n,n,n)); return 0; }