89 条题解
-
1
Lifi LV 10 @ 2019-08-05 13:33:56
唉，边界开小了。从下往上，记得初始化-INF。
#include <iostream> #include <cstring> using namespace std; int n,m; int desk[300][300]; int dp[300][300];//到达ij点的最大能量 int main() { cin>>n>>m; int i,j; for(i=0;i<n;i++) { for(j=0;j<m;j++) { cin>>desk[i][j]; } } memset(dp,129,sizeof(dp)); dp[n][m/2]=0; for(i=n-1;i>=0;i--) { for(j=0;j<m;j++) { dp[i][j]=dp[i+1][j]+desk[i][j]; if(j>0) { dp[i][j]=max(dp[i][j],dp[i+1][j-1]+desk[i][j]); } if(j<m-1) { dp[i][j]=max(dp[i][j],dp[i+1][j+1]+desk[i][j]); } } } int ans=-2e9; for(i=0;i<m;i++) { ans=max(ans,dp[0][i]); } cout<<ans<<endl; return 0; } -
1
大家都从上往下推
我来个从下往上
#include<bits/stdc++.h>
using namespace std;
#define xyf main
#define maxn 205
#define INF 2147483647int dp[maxn][maxn],n,m,Max=-INF;
int xyf()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>dp[i][j];
if(m&1)
{
for(int i=n-1;i>=1;--i)
for(int j=m/2-(n-i);j<=m/2+n-i+2;++j)
dp[i][j]+=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]));
for(int i=m/2+1-n;i<=m/2+1+n;++i)
Max=max(Max,dp[1][i]);
cout<<Max<<endl;
return 0;
}
for(int i=n-1;i>=1;--i)
for(int j=m/2-(n-i);j<=m/2+(n-i)+1;++j)
dp[i][j]+=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]));
for(int i=m/2-n+1;i<=m/2+n;++i)
Max=max(Max,dp[1][i]);
cout<<Max<<endl;
return 0;
} -
0
#include<iostream> using namespace std; int a[205][205],f[205][205]; int main(){ int n,m; int ans=-0x3f3f3f3f; cin>>m>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++) f[1][i]=a[1][i]; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j]; } } for(int i=n/2;i<=n/2+2;i++) ans=max(f[m][i],ans); cout<<ans; return 0; }属实水题 不过要注意细节：n是奇数 那么遍历到最下方时，只在三个数中找最大值即可
比如1 2 3 4 5 6 7
站在中间即在4的位置，要遍历3 4 5这三个位置，找最大值。
所以是n/2 n/2+1 n/2+2这三个位置
ans初值为负无穷，因为能量有可能为负 -
0
//第i行的状态只跟第i-1行有关，所以完全可以边输入边更新。
#include <bits/stdc++.h>
using namespace std;
int a[10000][10000],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++){
cin>>a[i][k];
a[i][k]+=max(a[i-1][k-1],max(a[i-1][k],a[i-1][k+1]));
}
cout<<max(a[n][m/2],max(a[n][m/2+1],a[n][m/2+2]));
return 0;
} -
0
#include<bits/stdc++.h> #define r(i,a,b) for(i=a;i<=b;i++) using namespace std; int main() { int a[300][300],n,m,i,j; scanf("%d%d",&n,&m); r(i,1,n) r(j,1,m) cin>>a[i][j]; r(i,2,n+1) r(j,1,m) a[i][j]+=max(a[i-1][j-1],max(a[i-1][j],a[i-1][j+1])); printf("%d",a[n+1][(m+1)/2]); return 0; } -
0
Kenny10001 LV 7 @ 2016-05-19 16:59:35
-
0
qq790189732 LV 8 @ 2015-09-24 20:35:40
GTM的作者写了半天读反了，水水水。
-
0
var
a:array[0..200,0..200] of longint;
f:array[0..200,0..200] of longint;
i,j,n,m,ans,start:longint;function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;
function max3(a,b,c:longint):longint;
var
d:longint;
begin
d:=max(a,b);
max3:=max(d,c);
end;
beginreadln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
start:=(m+1) shr 1;
fillchar(f,sizeof(f),128);
for i:=1 to m do
if abs(i-start)<=1 then f[n,i]:=a[n,i];
for i:=n-1 downto 1 do
begin
for j:=1 to m do
if (j>1) and (j<m) then f[i,j]:=max3(f[i+1,j-1],f[i+1,j+1],f[i+1,j])+a[i,j]
else if j=1 then f[i,j]:=max(f[i+1,j+1],f[i+1,j])+a[i,j]
else f[i,j]:=max(f[i+1,j],f[i+1,j-1])+a[i,j]
end;
for i:=1 to m do
if f[1,i]>ans then ans:=f[1,i];
writeln(ans);
end.哎，如此水题，竟然WA了一次。
究其原因，是最后一层初始化有错误，f[n,i]必须置为-oo（当abs(start-i)>1）
因为其他点是不能转移过来的。
写题解，是为了加深印象。
明天就要NOIP普及组复赛了，希望DP不要出岔子！ -
0
var
a:array[0..201,0..201]of longint;
i,j,n,m,s:longint;function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
for i:=1 to m do a[n+1,i]:=0;
for i:=1 to n+1 do
begin
for j:=1 to m do
a[i,j]:=a[i,j]+max(max(a[i-1,j-1],a[i-1,j]),a[i-1,j+1]);
end;
writeln(a[n+1,(m div 2)+1]);
end.
longint和integer的区别就是20到AC -
0
theniceboy LV 7 @ 2012-10-02 18:25:16
编译通过...
├ 测试数据 01：答案正确... (0ms, 908KB)
├ 测试数据 02：答案正确... (0ms, 908KB)
├ 测试数据 03：答案正确... (0ms, 908KB)
├ 测试数据 04：答案正确... (0ms, 908KB)
├ 测试数据 05：答案正确... (0ms, 908KB)
├ 测试数据 06：答案正确... (0ms, 908KB)
├ 测试数据 07：答案正确... (0ms, 908KB)
├ 测试数据 08：答案正确... (0ms, 908KB)
├ 测试数据 09：答案正确... (0ms, 908KB)
├ 测试数据 10：答案正确... (0ms, 908KB)
---|---|---|---|---|---|---|---|-
Accepted / 100 / 0ms / 908KB#include
using namespace std;
long long max(long long a,long long b){return a>b?a:b;}
long long a[210][210],f[210][210],m,n,i,j;
int main()
{
cin>>m>>n;
for(i=1;ia[i][j];}
}
for(i=1;i -
0
abc1405abc LV 8 @ 2010-03-05 20:37:03
var
i,j,k,l,n,m,x,y,z:longint;
f,a:array[0..210,0..210] of longint;procedure init;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a);
readln;
end;
fillchar(f,sizeof(f),0);
end;function max(x,y,z:longint):longint;
begin
max:=x;
if max -
0
program p1364;
var a,f:array[0..205,0..205] of longint;
i,j,k,l,m,n,ans:longint;
function max(x,y,z:longint):longint;
begin
max:=-maxlongint;
if x>max then max:=x;
if y>max then max:=y;
if z>max then max:=z;
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(a);
for i:=0 to n+1 do
for j:=0 to m+1 do f:=-maxlongint div 40;
f[n+1,m div 2+1]:=0;
for i:=n downto 1 do
for j:=1 to m do
f:=max(f,f,f)+a;
ans:=-maxlongint;
for i:=1 to m do
if f[1,i]>ans then ans:=f[1,i];
writeln(ans);
end. -
0
program p1364;
var
i,j,l,m,n:integer;
a,f:array[1..2000,1..2000] of longint;
function max(ql,q,qr,b:longint):longint;
var z:longint;
begin
z:=ql;
if q>z then z:=q;
if qr>z then z:=qr;
max:=z+b;
end;
function max2(ql,qr,b:longint):longint;
var z:longint;
begin
z:=ql;
if z -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
注意：是从最后一行的中间位置的下方开始，不是从最后一行的中间位置开始！！ -
0
guori12321 LV 8 @ 2009-11-01 19:05:28
这么水的题，做了快50min了。
初值又赋小了，注意菜的初值也要赋-maxlongint,不然挂一个点。
刚开始没看清，以为第一行只吃一盘，结果DEBUG时手工模拟下来都不对。
读题认真，构思谨慎，CODE要快。。。我的习惯啊！！！
Lifi
LV 10
@ 2019-08-05 13:33:56
