专栏首页随笔记录(c#解法)题解洛谷P1004(c++解法)方格取数

(c#解法)题解洛谷P1004(c++解法)方格取数

①先看一下出题日期(毕竟是NOIP的题目,有一定的水准),然后发现是2000年的普及第四题

我们要知道的是,好像比较前面的几年由于1999的数塔IOI问题后,接下来几年的最后一两题都很喜欢出DP

所以,我们首先看一下题目的内容,求路径最大的方法,这时候就要想到DP或者DFS

②然后我们发现题目的数据规模不大,n<=9,所以我们可以考虑用DFS或者DP都可以

但是鉴于 "好像比较前面的几年由于1999的数塔IOI问题后,接下来几年的最后一两题都很喜欢出DP "

我们觉得用DP会比较好

③而且,NOIP的压轴DP题你想要2维过(在考场上是很难想出来的)

所以我们考虑高维

④我们找到一个东西叫做四维DP,因为这题是两个人走,我们思考一下能不能单纯用两个人的模拟过a呢?

显然是可以的,我们记f[i][j][k][l]表示第1条路线的i,j走法和第2条路线的k,l走法

显然我们可以两个人一起走,复杂度最多就是999*9=6561(哈哈哈时间复杂度这么低)

所以我们就用这个方法了!

⑤然后我们思考动归方程的写法:

第1条路线只可能是从i-1,j或者i,j-1转移,第2条路线也只可能从k-1,l或者k,l-1转移

而且因为是2个人走,如果走到一点我们的那个点就要打标记说那点上面的值为0

所以我们得到了我们的动归方程(注意:万一i,j与k,l相同这是要小心的!)

f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1])+a[i][j]+a[k][l]; 1 代码如下:

#include<bits/stdc++.h>
 using namespace std;
 int n,x,y,val,ans=0,maxn,f[12][12][12][12],a[12][12];//a[i][j][k][l]表示两个人同时走,一个走i,j 一个走k,l
 int main(){
 scanf("%d",&n);
 memset(a,0,sizeof a);
 while(1){
 scanf("%d%d%d",&x,&y,&val);
 if(x0&&y0&&val0)break;
 a[x][y]=val;
 }
 for(int i=1;i<=n;i++){
 for(int j=1;j<=n;j++){
 for(int k=1;k<=n;k++){
 for(int l=1;l<=n;l++){
 f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i][j-1][k-1][l],max(f[i-1][j][k][l-1],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
 if(ik&&j==l)f[i][j][k][l]-=a[i][j];
 }
 }
 }
 }
 printf("%d\n",f[n][n][n][n]);
 return 0;
 }

————————————————

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Berries DP CodeForces_1Berries348E Phoenix and

    所以问题就变成了n个树,每棵树可以选择用不用同树框。这其实就是一个01背包的变形。

    w4979的博客
  • Berries DP CodeForces_1Berries348E Phoenix and

    所以问题就变成了n个树,每棵树可以选择用不用同树框。这其实就是一个01背包的变形。

    w4979的博客
  • public static Object service(String url, World至浏览

    生产环境,已经运行了好几年,一直没有问题。最近频繁奔溃(一般是连续运行好几天才奔溃一次)。boost 返回的 奔溃显示是 invaild_charset gbk...

    w4979的博客
  • codeforces 1423K(数学+差分数组预处理)

    dejavu1zz
  • codeforces 1423K(数学+差分数组预处理)

    显然,我们需要筛出所有质数。由于题目的范围太大,所以我们可以预处理出来答案,对于每次询问,直接输出答案即可。预处理可以使用差分数组来完成。

    dejavu1zz
  • 2018年奇虎360春招笔试题--玫瑰花

    郭耀华
  • 2018年奇虎360春招笔试题--玫瑰花

    这道题,第一感觉想用排列组合做,但是想了好久,没想到解决办法(刚刚考试的时候没有答出来)。后来想了一下应该使用动态规划来做。 我们首先分析一下情况: 1.当K>...

    郭耀华
  • codeforces 1133D (map+精度控制)

    移项后得到公式:\frac{b[i]}{-a[i]}=d,显然我们直接使用map来统计b[i]/a[i]的个数即可。如果a[i]为0,则不符合题意;如果a[i]...

    dejavu1zz
  • 1212 最大公约数

    1212 最大公约数  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白银 Silver 题目描述 Description 求两个数A和...

    attack
  • DP专题7 | 没有上司的舞会 洛谷1352(树形DP)

    本篇继续咱们的DP专题,树形DP入门。动态规划每一个类型的DP都是深坑,期望童鞋们自己在这个系列的基础上多花时间进行拓展,学习愉快~

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券