59 条题解
-
1Lifi LV 10 @ 2019-09-13 20:37:36
改一下题,树的高度为0,1,2.
则DP【i】【j】【0】为第i棵树高度为j时且前一棵树比i矮的最大值。
同理DP【i】【j】【1】为第i棵树高度为j时且前一棵树比i高的最大值。
第一个位置单独拿出来做成环条件判断。#include <iostream> #define LL long long using namespace std; int n; LL dp[100005][3][2]={0}; int main() { int i; LL ans=0; cin>>n; int a0,b0,c0,a,b,c; cin>>a0>>b0>>c0; for(i=1;i<n;i++) { cin>>a>>b>>c; dp[i][0][1]=max(dp[i-1][1][0],dp[i-1][2][0])+a; dp[i][1][0]=dp[i-1][0][1]+b; dp[i][1][1]=dp[i-1][2][0]+b; dp[i][2][0]=max(dp[i-1][0][1],dp[i-1][1][1])+c; } ans=max(ans,dp[n-1][0][1]+max(b0,c0)); ans=max(ans,dp[n-1][1][0]+a0); ans=max(ans,dp[n-1][1][1]+c0); ans=max(ans,dp[n-1][2][0]+max(a0,b0)); cout<<ans<<endl; return 0; }
-
12018-08-19 21:47:49@
来一份记忆化搜索[思维难度超低的~]
#include<bits/stdc++.h> #define _ 100008 #define R register using namespace std; int n,val[4][_],f[_][4][4][2],tp[_],tot; int dfs(R int dr,R int lst,R int one,R int up){ if(f[dr][lst][one][up]!=-1) return f[dr][lst][one][up]; if(dr==n+1){ return ((up&&lst>one)||((!up)&&lst<one))?0:-1; } R int r=-1; if(dr==1){ for(R int i=1;i<=3;i++){ int c=dfs(dr+1,i,i,0); if(c!=-1) r=max(r,c+val[i][dr]); } } else{ if(dr==2){ for(R int i=lst+1;i<=3;i++){ int c=dfs(dr+1,i,one,1); if(c!=-1) r=max(r,c+val[i][dr]); } for(R int i=lst-1;i>=1;i--){ int c=dfs(dr+1,i,one,0); if(c!=-1) r=max(r,c+val[i][dr]); } } else{ if(up){ for(R int i=lst-1;i>=1;i--){ int c=dfs(dr+1,i,one,0); if(c!=-1) r=max(r,c+val[i][dr]); } } else{ for(R int i=lst+1;i<=3;i++){ int c=dfs(dr+1,i,one,1); if(c!=-1) r=max(r,c+val[i][dr]); } } } } //if(dr==4) // cout<<dr<<' '<<lst<<' '<<one<<' '<<r<<' '<<endl; return f[dr][lst][one][up]=r; } int main(){ cin>>n;memset(f,-1,sizeof(f)); for(int i=1;i<=n;i++)scanf("%d%d%d",&val[1][i],&val[2][i],&val[3][i]); cout<<dfs(1,0,0,0); }
-
12017-05-26 09:07:23@
0.1s过全部。。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; int f[200001][5][2],n,v1[200001],v2[200001],v3[200001],ans=0; int main() { scanf("%d",&n); For(i,1,n) scanf("%d%d%d",&v1[i],&v2[i],&v3[i]); For(i,2,n) { f[i][1][1]=max(f[i-1][2][0]+v1[i],f[i-1][3][0]+v1[i]); f[i][3][0]=max(f[i-1][2][1]+v3[i],f[i-1][1][1]+v3[i]); f[i][2][0]=f[i-1][1][1]+v2[i]; f[i][2][1]=f[i-1][3][0]+v2[i]; } ans=max(ans,f[n][1][1]+v2[1]);ans=max(ans,f[n][3][0]+v2[1]); ans=max(ans,max(f[n][2][0]+v1[1],f[n][3][0]+v1[1])); ans=max(ans,max(f[n][2][1]+v3[1],f[n][1][1]+v3[1])); printf("%d",ans); }
-
02016-08-23 20:55:46@
没看见**环**导致WA并RP--的路过
贴一份带缩进代码
```c++
#include <bits/stdc++.h>
using namespace std;int a[100005][4], n;
int g[100005][4][4], f[100005][4][4];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &a[i][1], &a[i][2], &a[i][3]);
memset(g, 0, sizeof g);
memset(f, 0, sizeof f);
for (int j = 1; j <= 3; j++) {
f[1][j][j] = a[1][j];
g[1][j][j] = a[1][j];
}
for (int i = 2; i <= n; i++)
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++)
for (int l = 1; l <= 3; l++) {
if (j > k) f[i][j][l] = max(f[i][j][l], g[i-1][k][l]+a[i][j]);
if (j < k) g[i][j][l] = max(g[i][j][l], f[i-1][k][l]+a[i][j]);
}
}
int ans = 0;
for (int i = 1; i <= 3; i++)
for (int b = 1; b <= 3; b++){
if (b > i) ans = max(ans, g[n][i][b]);
if (b < i) ans = max(ans, f[n][i][b]);
}
cout << ans << endl;
return 0;
}
``` -
02012-10-27 08:38:30@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms啦啦啦 呵呵呵
-
02009-11-09 14:57:33@
模子很多,就不要晒着相同的了。。
-
02009-11-09 14:01:39@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msprogram ex;
var i,j,n,ans:longint;
a:Array[1..100000,1..3]of longint;
f:Array[1..100000,1..4]of longint;
mark:array[0..1,1..4]of longint;procedure init;
var i,j:longint;
begin
readln(n);
for i:=1 to n do readln(a,a,a);
end;function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;procedure dp(x:longint);
var i,j,k:longint;
begin
for i:=1 to 4 do
f[1,i]:=-maxlongint;
f[1,x]:=a[1,x div 2+1];
for i:=2 to n do
begin
{1} f:=max(f,f)+a;
{2.1} f:=f+a;
{2.2} f:=f+a;
{3} f:=max(f,f)+a;
end;
end;procedure main;
var i,j:longint;
begin
ans:=0;
dp(1);
ans:=max(f[n,2],f[n,4]);
dp(2);
ans:=max(ans,f[n,1]);
dp(3);
ans:=max(ans,f[n,4]);
dp(4);
ans:=max(ans,max(f[n,1],f[n,3]));
end;procedure print;
var i,j:longint;
begin
writeln(ans);
end;begin
init;
main;
print;
end. -
02009-10-31 20:13:15@
还要环的唉..
用f表示
种第i颗树 最后一颗高度是j(j=1,2,3)
k=0表示第i棵树比i-1棵低 k=1表示第i棵树比i-1棵高
第一棵树高度是l(要环的啊啊啊)var i,j,k,l,m,n,ans:longint;
f:Array[0..100000,1..3,0..1,1..3]of longint;
a:array[0..100000,1..3]of longint;function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;begin
readln(n);
readln(a[1,1],a[1,2],a[1,3]);
f[1,1,0,1]:=a[1,1]; f[1,2,0,2]:=a[1,2]; f[1,2,1,2]:=a[1,2]; f[1,3,1,3]:=a[1,3];
for i:=2 to n do
begin
readln(a,a,a);
for j:=1 to 3 do
begin
f:=max(f,f)+a;
f:=f+a;
f:=f+a;
f:=max(f,f)+a;
end;
end;
if f[n,1,0,2]>ans then ans:=f[n,1,0,2];
if f[n,1,0,3]>ans then ans:=f[n,1,0,3];
if f[n,2,0,3]>ans then ans:=f[n,2,0,3];
if f[n,2,1,1]>ans then ans:=f[n,2,1,1];
if f[n,3,1,1]>ans then ans:=f[n,3,1,1];
if f[n,3,1,2]>ans then ans:=f[n,3,1,2];
writeln(ans);end.
30行的..
嘿嘿
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-10-22 16:53:51@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:运行超时...
├ 测试数据 08:运行超时...
├ 测试数据 09:运行超时...
├ 测试数据 10:运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:60 有效耗时:0ms他居然说我过了
郁闷 就当过了。。。 -
02009-10-22 16:23:25@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 72ms
├ 测试数据 09:答案正确... 41ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:138ms一次AC 感觉很不错
嘿嘿 -
02009-09-13 20:19:18@
膜拜voyagec2的解法,我稍稍概括了下,39行,0ms
-
02009-09-06 13:54:18@
Var
F,H:array[1..100000,1..3,0..1]of longint;
A:array[1..100000,1..3]of longint;
N:longint;Procedure Init;
Var
I:longint;
Begin
Readln(N);
For i:=1 to N do readln(a,a,a);
End;Procedure Dp;
Var
I,Ans:longint;
Begin
F[1,1,0]:=A[1,1];
F[1,2,0]:=A[1,2];
F[1,2,1]:=A[1,2];
F[1,3,1]:=A[1,3];
H[1,1,0]:=1;
H[1,2,0]:=2;
H[1,2,1]:=2;
H[1,3,1]:=3;
For i:=2 to N do
Begin
If F>F then
Begin
F:=F+A;
H:=H;
End
Else
Begin
F:=F+A;
H:=H;
End;
F:=F+A;
H:=H;
F:=F+A;
H:=H;
If F>F then
Begin
F:=F+A;
H:=H;
End
Else
Begin
F:=F+A;
H:=H;
End;
End;
Ans:=0;
If (F[N,1,0]>Ans) and (H[N,1,0]>1) then Ans:=F[N,1,0];
If (F[N,2,0]>Ans) and (H[N,2,0]>2) then Ans:=F[N,2,0];
If (F[N,2,1]>Ans) and (H[N,2,1]Ans) and (H[N,3,1] -
02009-07-31 18:23:58@
明摆的DP....怎么是其他类的....
-
02009-06-02 07:59:27@
为了方便,把程序的常数的写的有点大了……
6k上挂了,puppy来了就AC了,但没秒闪…… -
02009-05-15 23:21:25@
方程:
f:=max(f,f)+a;
f:=f+a;
f:=f+a;
f:=max(f,f)+a; -
02008-11-13 10:17:59@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02008-11-12 20:30:34@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 9ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:34msvar
v:array[1..100000,1..3]of int64;
dp:array[1..100000,-2..3]of int64;
i,j,k,n:longint;
ans:int64;
function max(a,b:int64):int64;
begin
if a>b then max:=a
else max:=b;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(v[i][1],v[i][2],v[i][3]);
end;
fillchar(dp,sizeof(dp),0);
for i:=2 to n do
begin
if i=2 then
begin
// 1
dp:=v[1,1]+v[2,2];
dp:=v[1,1]+v[2,3];
end
else
begin
dp:=max(dp+v,dp+v);
dp:=max(dp+v,dp+v);
dp:=dp+v;
dp:=dp+v;
end;
end;
ans:=max(dp[n,2],dp[n,3]);fillchar(dp,sizeof(dp),0);
for i:=2 to n do
begin
if i=2 then
begin
// 2
dp:=v[1,2]+v[2,1];
dp:=v[1,2]+v[2,3];
end
else
begin
dp:=max(dp+v,dp+v);
dp:=max(dp+v,dp+v);
dp:=dp+v;
dp:=dp+v;
end;
end;
if max(dp[n,-1],dp[n,3])>ans then ans:=max(dp[n,-1],dp[n,3]);fillchar(dp,sizeof(dp),0);
for i:=2 to n do
begin
if i=2 then
begin
// 3
dp:=v[1,3]+v[2,2];
dp:=v[1,3]+v[2,1];
end
else
begin
dp:=max(dp+v,dp+v);
dp:=max(dp+v,dp+v);
dp:=dp+v;
dp:=dp+v;
end;
end;
if max(dp[n,-1],dp[n,-2])>ans then ans:=max(dp[n,-1],dp[n,-2]);
write(ans);
end. -
02008-11-11 17:02:42@
看了题解才做出来的 ,不错的题啊,。虽然开始就往递推的方向想,但始终没能想出来,因为不会处理环状结构这个问题。。。
我是按 voyagec2 的方法写的 。0S搞定 -
02008-11-11 16:27:09@
第一次tle了4个。。。发现自己打错。。做了n次动规。。改成4,全0...
-
02008-11-11 14:49:47@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:运行超时...
├ 测试数据 04:运行超时...
├ 测试数据 05:运行超时...
├ 测试数据 06:运行超时...
├ 测试数据 07:运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 08:运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 09:运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 10:运行时错误...| 错误号: 202 | 堆栈溢出错
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:20 有效耗时:0ms