zy 送画

问题描述
话说在军训的倒数第二天,zy终于下定决心要将画了 10天之久的画像送给他心怡的法
学院mm。但是,他不敢自己一个人去,倒霉的 kk 只能和他一起去了。不过,为了表现的有
诚意,kk和zy不能走在一起,要不然被对方看见就不好了。那么到底要怎么走呢?zy给了
kk 一幅地图,他把学校分成了 n*m 个格子,对于每个格子,zy 写下了一个数字表示他对于
这个格子的好感度(好感度当然是 zy 自己定义的) ,入口在左上角(1,1)点,出口在右下
角(n,m),zy 和 kk 需要从左上角一起出发,在右下角会和,因为 zy 非常害羞,所以中间
kk和zy都只向右或向下走,这样走完全程的时间最短, 但中间两人不能走到同一个格子上。
经过深思熟虑,他决定,需要他和 kk 走的路的好感度总和最大才是最好。现在,zy 和 kk
希望你能告诉他们两个人各自要走那一条路。为了简化问题,你只需告诉他们两个好感度总
和就可以了。你可以假设mm一定会在zy的路上。
 
输入描述
第一行两个整数 n,m。
接下来n行每行 m个整数,每两个整数之间用一个空格隔开。
 
输出描述
一行一个整数表示最大好感度和。注意,起点和终点的好感度值只计入一次。

样例输入
3 4
1 2 3 4
5 6 7 8
9 10 11 12
 
样例输出
71
 
数据范围
2<=n,m<=50。
好感度为10000以内的正整数。

这道题与08年noip传纸条相当相似,虽然我并没有做过传纸条。

我是用递归做的,枚举两个人在一个时间点到的点,

如果相同就返回。

设置坐标0,0为之前已经到了终点,就只需要搜另一个人的路径了,

当某人到了终点时,下一次坐标就会为0,0,也是只需搜另一个人的路径了。

再加记忆数组,过完。

 #include <iostream>
#include <fstream>
#include <cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std; ifstream fin("paint.in");
ofstream fout("paint.out"); int cnt_heng=,cnt_lie=;
int jiyi[][][][]={};
int jv[][]; int dp(int he1,int zo1,int he2,int zo2){
if(he1==cnt_heng&&zo1==cnt_lie)
if(he2==cnt_heng&&zo2==cnt_lie)return jv[cnt_heng][cnt_lie];
if(he1==he2&&zo1==zo2)return ;
if(he1>cnt_heng||he2>cnt_heng)return ;
if(zo2>cnt_lie||zo1>cnt_lie)return ;
if(jiyi[he1][zo1][he2][zo2]!=)return jiyi[he1][zo1][he2][zo2];
int a[]={,},b[]={,};
int tem=;
if(he1==cnt_heng&&zo1==cnt_lie){
if(he2==&&zo2==)return ;
for(int x=;x<=;x++)
tem=max(tem,dp(,,he2+a[x],zo2+b[x]));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[cnt_heng][cnt_lie]+jv[he2][zo2];
} if(he2==cnt_heng&&zo2==cnt_lie){
if(he1==&&zo1==)return ;
for(int x=;x<=;x++)
tem=max(tem,dp(he1+a[x],zo1+b[x],,));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[cnt_heng][cnt_lie]+jv[he1][zo1];
}
if(he1==&&zo1==){
for(int x=;x<=;x++)
tem=max(tem,dp(,,he2+a[x],zo2+b[x]));
jiyi[he1][zo1][he2][zo2]=tem+jv[he2][zo2];
return tem+jv[he2][zo2];
}
if(he2==&&zo2==){
for(int x=;x<=;x++)
tem=max(tem,dp(he1+a[x],zo1+b[x],,));
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1];
return tem+jv[he1][zo1];
} for(int x=;x<=;x++)
for(int y=;y<=;y++){
tem=max(tem,dp(he1+a[x],zo1+b[x],he2+a[y],zo2+b[y]));
}
jiyi[he1][zo1][he2][zo2]=tem+jv[he1][zo1]+jv[he2][zo2];
return tem+jv[he1][zo1]+jv[he2][zo2];
} int main(int argc, char** argv) {
fin>>cnt_heng>>cnt_lie;
for(int x=;x<=cnt_heng;x++)
for(int y=;y<=cnt_lie;y++)fin>>jv[x][y]; int ans=dp(,,,);
ans+=jv[][];
cout<<ans;
fout<<ans; return ;
}
上一篇:centos6.5和centos7如何搭建php环境


下一篇:Java中五种遍历HashMap的方式