（以“ 分类:棋盘动态规划 ==摘要== {{信息题|传纸条|http://www.codevs.cn/problem/1169/|1|100|time=2014/11/28 20:21:12|20|算法错误}} ==题意== 从(1,...”为内容创建页面） |
小 （格式） |
||
| 第2行： | 第2行： | ||
[[分类:棋盘动态规划]] | [[分类:棋盘动态规划]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|传纸条|http://www.codevs.cn/problem/1169/|1|100|time=2014/11/28 20:21:12 | + | {{信息题|传纸条|http://www.codevs.cn/problem/1169/|1|100|time=2014/11/28 20:21:12|算法错误|20}} |
==题意== | ==题意== | ||
从(1,1)传纸条到(n,m)并返回，每个点只能经过一遍，求好感度最大值。 | 从(1,1)传纸条到(n,m)并返回，每个点只能经过一遍，求好感度最大值。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 传纸条 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/28 20:21:12 | 算法错误（20） |
从(1,1)传纸条到(n,m)并返回，每个点只能经过一遍，求好感度最大值。
CloudLunaro - o - o
| |
o o - o
|
o - o
o - o - o
|
o
dp[i][j][sum]=v[i][sum-i]+v[j][sum-j]+
max{
dp[i-1][j][sum-1]+
dp[i][j-1][sum-1]+
dp[i-1][j-1][sum-1]+
dp[i][j][sum-1]
};
//dp[i][j][sum]表示两条路线分别走到(i,sum-i)(j,sum-j)时候的最大好感度
| 1169（记忆化搜索，错误写法）.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
int M[100][100][3]={},used[100][100]={},n,m,v[100][100];
void dfs(const int &x,const int &y,const int &t,const int &c)
{
if(used[x][y])
return;
if((!(x==1&&y==1))&&(!(x==n&&y==m)))
used[x][y]=1;
if(M[x][y][t]>c&&M[x][y][t])return;
M[x][y][t]=c;
if(x==n&&y==m)
{
if(t==1)
dfs(1,1,2,c);
return;
}
if(x+1<=n)
dfs(x+1,y,t,c+v[x+1][y]);
if(y+1<=m)
dfs(x,y+1,t,c+v[x][y+1]);
used[x][y]=0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&v[i][j]);
}
}
dfs(1,1,1,v[1][1]);
printf("%d\n",M[n][m][2]-v[n][m]);
return 0;
}
|
| 1169.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,dp[100][100][200]={},v[100][100]={};
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&v[i][j]);
for(int sum=2;sum<n+m;++sum)
for(int i=max(1,sum-n);i<=min(sum-1,m);++i)
for(int j=max(1,sum-n);j<=min(sum-1,m);++j)
{
if(i==j)continue;
if(i-1!=j)
dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j][sum-1]+v[i][sum-i]+v[j][sum-j]);
if(i!=j-1)
dp[i][j][sum]=max(dp[i][j][sum],dp[i][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]);
dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]);
dp[i][j][sum]=max(dp[i][j][sum],dp[i][j][sum-1]+v[i][sum-i]+v[j][sum-j]);
}
printf("%d",max(dp[m-1][m][n+m-1],dp[m][m-1][n+m-1]));
}
|