#C241017C. [NOIP2000 提高组] 方格取数

标签（Label）

• 动态规划

网址（Website）

P1004 [NOIP2000 提高组] 方格取数 - 洛谷

「NOIP2000 提高组」 - Super

题解（Solution）

加强版在这里→ 方格取数（加强版） - WolfDeer

$\qquad$很明显这道题不能先跑一次再跑一次，只能双管齐下，又发现 $n$ 的值域很小。

$\qquad$想过设 $f[a][b][c][d]$ ，表示两次走分别的位置，但自己不知道怎么的就开始怀疑其这种方法的正确性了，然后又开始乱搞。。。(•_•)

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 12;
bool ST;

int f[N][N][N][N];
int p[N][N];
int n;

void solve(){
	n = rd();{int x,y,v;while(!!(x=rd()) && !!(y=rd()) && !!(v=rd())){p[x][y] = v;}}
	For(a,1,n) For(b,1,n) For(c,1,n) For(d,1,n){
		f[a][b][c][d] = max({f[a-1][b][c-1][d], f[a-1][b][c][d-1], f[a][b-1][c-1][d], f[a][b-1][c][d-1]}) + p[a][b] + p[c][d];
		if(a==c && b==d) f[a][b][c][d] -= p[a][b];
	}printf("%lld\n",f[n][n][n][n]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}