洛谷 P1006 传纸条【夜间感想】

代码
https://www.luogu.org/problemnew/show/P1006
思路就是双线dp,处理好边界即可,
dp(当前步数,1右几步,2右几步)
当成大家都从左上走到右下即可。
(代码后是一些感想)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
	int a[52][52];
	int dp[104][52][52];
int main(){
	//freopen("testdata (3).in", "r", stdin); 
	int m, n;
	cin >> m >> n;

	memset(a, 0, sizeof(dp));
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n + m - 3; i++)
		for (int j = min(n, i); j >= 0 && (i - j) <= m; j--)
			for (int k = min(n, i); k >= 0 && (i - k) <= m; k--){
				dp[i][j][k] = 0;
				if ((j - 1 != k - 1 || j - 1 == 0) && (j - 1 >= 0) && (i - 1 >= 0)) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - 1]);//都向右走 
				if ((j - 1 != k || j - 1 == 0) && (j - 1 >= 0) && (i - k - 1 >= 0)) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k]);//1右2下 
				if ((j != k - 1 || j == 0) && (k - 1 >= 0) && (i - j - 1 >= 0)) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1]);//1下2右 
				if ((j != k || j == 0) && (i - j - 1 >= 0) && (i - k - 1 >= 0)) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);//都向下 
				if(j != k) dp[i][j][k] += a[i - j][j] + a[i - k][k];
				else dp[i][j][k] = 0;
				//if(i > 33) cout << "i,j,k:" << i << ',' << j << ',' << k << ':' << dp[i][j][k] << endl;
			}
		int ans = 0;
		for (int i = 0; i <= m + n - 3; i++)
		for (int j = 0; j <= m + n - 3; j++)
			if (i != j) ans =  max(dp[m + n - 3][i][j], ans);
	cout << ans;

}

其实贴出这么一段代码,并不是证明我有多厉害,相反我觉得我退步不少。知道身边的同龄人有不少竞赛大牛之后我彻夜难眠,想了很久,觉得一直以来自己实在是太“事儿”,好像每个领域都会去涉猎一下,但却一无所长!于是我退出了许多QQ群,断绝了与大多数没有前途、自己不适合的而且还有可能耽误自己学习的领域的联系,因为我想专注于一件事,更因为我想学好数学,学好计算机,学好两者兼容的“算法”。这样果断的决定后我辗转难眠,不是因为后悔,而是因为自己决定要在今晚开始改变什么,于是我在一点半的时候,在激情的驱使下爬下床,把这一题给A掉了。

这一题很难吗?不难,对于各位大牛可能就五分钟左右的事,但我用了两个小时,说明什么?说明我其实很水...对,我一直以来在我的博客发题解,其实不是讲解,更多的是我的成长的记录,我在算法学习这条路上的记录。如果你看过我的提交,你会发现我现在很多东西都不会,代码质量也很差。我自己也觉得如此。直到有一次我想着与别人的差距,我几乎选择了放弃,但所谓的放弃,我在今天晚上终于明白只是由于我自己的懦弱。

于是我决定在这条路上走下去。也许今天我A掉这道题,花了两个小时,很菜,但我在成长,我没有选择逃避,没有再把时间花在不该花的领域上。

我能成为大牛吗?不知道。

但我愿放手一搏。

与君共勉。

A/B,朹方

2019年4月24日 03点45分

我还没有学会写个人说明!

发表评论

电子邮件地址不会被公开。 必填项已用*标注