175 条题解
-
0
wangshizhou LV 8 @ 2009-08-20 22:24:35
数据弱 ？？
-
0
J. Wallace LV 6 @ 2009-08-12 18:01:22
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
...写了三取方格数之后来写这个，好像还有点吃力。。。掌握得真不好 -
0
xiaowu2008 LV 8 @ 2009-08-12 15:24:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 119ms
├ 测试数据 08：答案正确... 212ms
├ 测试数据 09：答案正确... 197ms
├ 测试数据 10：答案正确... 181ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：709ms
还好，ms没过1000，贴个题解。。。。。。
ORZ0ms的......
#include
using namespace std;
/*ifstream fin(".in");
ofstream fout(".out");*/
int a[52][52],dp[52][52][52][52]={0},n,m,oi,op,ou,ol;
int kk[4][4]={0,-1,-1,0,-1,0,-1,0,0,-1,0,-1,-1,0,0,-1};
int main()
{
int i,j,k,p;
cin>>n>>m;
for(int i=1;ia[i][j];
for(int i=1;i -
0
caojiahao2 LV 9 @ 2009-08-10 07:33:24
{多进程DP：1、按对角线划分阶段：动归方程： f[x1,x2,k]:=max(f[x1-1,x2-1,k-1],f[x1-1,x2,k-1],f[x1,x2,k-1],f[x1,x2-1,k-1])+a[x1,k+2-x1]+a[x2,k+2-x2]
2、限制条件：x1x2，当x1-1=x2或者x2-1=x1时去掉这种情况，因为一个点不能走两次（将其赋值为0即可）
3、每个阶段枚举所有坐标时的上界与下界：
if (kn-1)then begin max:=m;min:=k+2-n;end;
4、横坐标与纵坐标关系：y=k+2-x，所以在各个阶段中横坐标确定，纵坐标即确定，枚举纵坐标即可}
var
x1,x2,k,l,m,n,max,min,result,i,j:longint;
a:array[-2..52,-2..52]of integer;
f:array[-2..52,-2..52,-2..52]of longint;
function fmax(a,b,c,d:longint):longint;
begin
fmax:=0;
if a>fmax then fmax:=a;
if b>fmax then fmax:=b;
if c>fmax then fmax:=c;
if d>fmax then fmax:=d;
end;
procedure fmaxmin;
begin
if (kn-1)then begin max:=m;min:=k+2-n;exit;end;
end;
begin
readln(n,m);
fillchar(a,sizeof(a),0);
fillchar(f,sizeof(f),0);
for j:=1 to n do
begin
for i:=1 to m do
read(a);
readln;
end;
f[1,1,0]:=a[1,1];
for k:=1 to n+m-3 do
begin
fmaxmin;
for x1:=min to max do
for x2:=min to max do
if x1x2 then
begin
if (x1-1x2)and(x1x2-1)then
begin
f[x1,x2,k]:=fmax(f[x1-1,x2-1,k-1],f[x1-1,x2,k-1],f[x1,x2,k-1],f[x1,x2-1,k-1])+a[x1,k+2-x1]+a[x2,k+2-x2];
continue;
end;
if (x1-1x2)and(x1=x2-1)then
begin
f[x1,x2,k]:=fmax(f[x1-1,x2-1,k-1],f[x1-1,x2,k-1],f[x1,x2,k-1],0)+a[x1,k+2-x1]+a[x2,k+2-x2];continue;
end;
if (x1-1=x2)and(x1x2-1)then
begin
f[x1,x2,k]:=fmax(f[x1-1,x2-1,k-1],0,f[x1,x2,k-1],f[x1,x2-1,k-1])+a[x1,k+2-x1]+a[x2,k+2-x2];
continue;
end;
end;
end;
writeln(f[m-1,m,n+m-3]);
end.
{优化空间时也可用滚动数组。这样可降到二维} -
0
wfh20050903 LV 4 @ 2009-08-07 23:35:14
#include"stdio.h"
#include"stdlib.h"
#define MAX(a,b) (a>b?a:b)
int a[60][60],dp[200][60][60];
int main()
{
int i,j,m,n,x1,x2,temp,max;
// freopen("输入.txt","r",stdin);
// freopen("输出.txt","w",stdout);
scanf("%d%d",&m,&n);
for(i = 1; i -
0
真的，很后悔当时没能想出来。
后来发现是高维DP，呵呵。现在看起来很简单。
以步数作为阶段，解决这一题，三取石子之类的就都变简单了。program message;
const dir:array [1..4,1..2] of shortint=((0,0),(-1,0),(0,-1),(-1,-1));
var
dp:array [0..100,1..50,1..50] of longint;
table:array [1..50,1..50] of integer;
yj,yk,tj,tk,m,n,i,j,k,l:integer;
t,max:longint;
begin
readln (m,n);
for i:=1 to m do begin
for j:=1 to n do read (table);
readln;
end;
fillchar (dp,sizeof(dp),0);
for i:=1 to m+n do for j:=1 to m do for k:=1 to m do begin
yj:=i+1-j;yk:=i+1-k;max:=-maxlongint;
if (yj>0) and (yk>0) and (yj0) then
if dp>max then max:=dp;
end;
dp:=max+t;
end;
end;
writeln (dp[m+n-1,m,m]);
end. -
0
var
n,m,k,l,i,j:longint;
a,b:array[0..101,0..101] of longint;
c:array[0..101] of integer;
f,ff:array[0..101,0..101] of longint;
function max(a,b,c:longint):longint;
begin
if a>b then if a>c then exit(a)
else exit(c)
else if b>c then exit(b)
else exit(c);
end;
begin
read(n,m);
for i:=1 to n do for j:=1 to m do read(a);
l:=n+m-1;
for i:=1 to n do
begin j:=1;
for k:=i downto 1 do begin b:=a[k,j];j:=j+1;c[i]:=c[i]+1;if j>m then break;end;
end;
for i:=n+1 to l do
begin j:=n;
for k:=i-n+1 to m do begin b:=a[j,k];j:=j-1;c[i]:=c[i]+1;end;
end;
f[1,2]:=b[2,1]+b[2,2];
for i:=3 to l-1 do
begin
for j:=1 to c[i]-1 do
for k:=j+1 to c[i] do
begin
if i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msCostFlow.
贡献两次WA..忘记把拆点后多的一半算在总点数里 - - -
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
直接裸奔网络流。。。
#include
#include
using namespace std;
const int V=5000,MaxV=200;
const int di[]={1,0},dj[]={0,1},inf=~0U>>1;
int Map[50][50][2]={0};
int A[50][50],N,M,cnt;
struct edge
{
int t,c,u;
edge* next,*op;
edge(int t,int c,int u,edge* n):t(t),c(c),u(u){next=n;}
}*E[V];
inline void addedge(int s,int t,int u,int c)
{
E=new edge(t,c,u,E);
E[t]=new edge(s,-c,0,E[t]);
E->op=E[t];E[t]->op=E;
}
void init()
{
cin>>N>>M;
for(int i=0;iA[i][j];
Map[i][j][0]=cnt++;
Map[i][j][1]=cnt++;
}
}
void make()
{
int t,u;
for(int i=0;iu))
return i->u-=d,i->op->u+=d,d;
return 0;
}
bool md()
{
int d=inf,c;
for(int i=0;inext)if(j->u && !v[j->t])
if((c=pi[j->t]+j->c-pi[i]) -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 25ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 72ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：210msvar m,n,i,j,k,l:integer; f:array[0..52,0..52,0..52,0..52]of integer;
a:array[0..51,0..51]of integer;
function max(w1,w2,w3,w4:integer):integer;
begin
max:=0;
if w1>w2 then max:=w1 else max:=w2;
if w3>max then max:=w3;
if w4>max then max:=w4;
end;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do read(a);
for i:=1 to m do
for j:=1 to n do
for k:=1 to m do
for l:=1 to n do
if (i=m)and(j=n)and(k=m)and(l=n) then f:=max(f,f,f,f)+a[m,n]
else
if (i=k)and(j=l) then f:=-maxint
else f:=max(f,f,f,f)+a+a[k,l];
write(f[m,n,m,n]);
end.
没秒杀! -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms空间上用2维 也可以，毕竟f[k,i,j]的状态只和上一层有关
var k,i,j,m,n,temp:longint;
a:array[0..100,0..100]of longint;
f:array[0..100,-1..99,-1..100]of longint;function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;begin
readln(m,n);
if(m=0)or(n=0) then begin writeln('0'); halt; end;for i:=0 to m+1 do
for j:=0 to n+1 do
a:=-1;
for i:=1 to m do
for j:=1 to n do
read(a);fillchar(f,sizeof(f),0);
f[2,1,2]:=a[1,2]+a[2,1];for k:=3 to n+m-2 do
for i:=1 to k-1 do
begin
if a=-1 then continue;for j:=i+1 to k do
begin
if a[j,k-j+1]=-1 then break;
if j-1=i then
begin
temp:=max(f[k-1,i-1,j],f[k-1,i-1,j-1]);
f[k,i,j]:=max(f[k-1,i,j],temp)+a+a[j,k-j+1];
end;
if j-1>i then
begin
temp:=max(f[k-1,i-1,j-1],f[k-1,i-1,j]);
f[k,i,j]:=max(temp,max(f[k-1,i,j],f[k-1,i,j-1]))+a+a[j,k-j+1];
end;
end;end;
writeln(f[m+n-2,m-1,m]);end.
-
0
Var
m,n,i,j,s,mm:Integer;
a:Array[1..50,1..50] Of Integer;
f:Array[1..99,0..50,0..50] Of Longint;Function Max(x,y:Longint):Longint;
Begin
If x>y Then Exit(x) Else Exit(y);
End;Begin
Readln(m,n);
For i:= 1 To m Do
Begin
For j:= 1 To n Do Read(a);
Readln;
End;
FillChar(f,SizeOf(f),0);
For s:= 2 To (m+n-1) Do
For i:= 1 To m Do
For j:= 1 To m Do
If (s+1-i>0) And (i>j) Then
Begin
mm:=f;
mm:=Max(mm,f);
mm:=Max(mm,f);
mm:=Max(mm,f);
f:=mm+a+a[j,s+1-j];
End;
Writeln(f[m+n-2,m-1,m]+f[m+n-2,m,m-1]);
End.就是DP饿！~~
-
0
SecretAgent LV 10 @ 2009-06-30 13:52:32
记忆化递规
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
cmykrgb123 LV 4 @ 2009-06-24 12:06:29
-
lambdacat @ 2016-11-04 13:26:34
发现一只郭家宝
-
wangshizhou
LV 8
@ 2009-08-20 22:24:35
