刷题记录:牛客NC16759[NOIP2000]方格取数

传送门:牛客

题目描述:

设有N*N的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出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

emmm,这道题和这道题的算法是一模一样的.可以先去做做那道题(在本博客中就不再赘述了,看那篇博客就行)

假设你已经做过那道题了.然后你回来做这道题,你会问,诶,有一个小问题,在那道题中我们的同一个点是不能被走两次的,但是在本题中我们的同一个点是可以走两次的,只不过我们值不能被累加两次而已

但是其实是没有关系的,因为有一个贪心的想法,那就是当我们的一个点被重复的走时,我们其实是不是最优解的.举一个小栗子:

如上图我们的1和2点走到右下角,我们的红线和蓝线是相交的,但是此时我们显然我们的红线加蓝线是没有蓝线加紫线来的更加优秀的.

并且注意此题中我们的起点和终点可能是有值的,所以不要忘记加上起点和终点

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int m,n;
int dp[120][60][60];
int a[60][60];
int main() {
	m=read();n=m;
	int num;int l,r;
	while(scanf("%d%d%d",&l,&r,&num)){
		if(l==0&&r==0&&num==0) break;
		a[l][r]=num;
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[2][1][1]=a[1][1];
	for(int sum=3;sum<=m+n-1;sum++) {
		for(int i=1;i<=m;i++) {
			for(int j=i+1;j<=m;j++) {
				int this_dp=dp[sum][i][j];
				this_dp=max(this_dp,dp[sum-1][i][j]);
				this_dp=max(this_dp,dp[sum-1][i-1][j]);
				this_dp=max(this_dp,dp[sum-1][i-1][j-1]);
				this_dp=max(this_dp,dp[sum-1][i][j-1]);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               
				if(this_dp==-1) continue;
				dp[sum][i][j]=this_dp+a[i][sum-i]+a[j][sum-j];
			}
		}
	}
	cout<<dp[m+n-1][m-1][m]+a[n][n]<<endl;
	return 0;
}