26 条题解
-
2
Sky1231 (sky1231) LV 10 @ 2017-07-31 14:11:11
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,m,t; int a[160+1]; int z[160+1]; int f[160+1][50+1]; int g[160+1][160+1]; int v[160+1][160*50+1]; int main() { while (~scanf("%d%d%d",&n,&m,&t)) { for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&z[i]); memset(g,0,sizeof(g)); for (int i=1;i<=n;i++) { memset(v,0,sizeof(v)); for (int j=i;j<=n;j++) for (int k=0;k<=(n-i+1)*t;k++) v[j][k]=max(v[j-1][k],((k>=a[j])?(v[j-1][k-a[j]]+z[j]):0)); for (int j=i;j<=n;j++) g[i][j]=v[j][(j-i+1)*t]; } memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=i-j+1;k++) f[i][j]=max(f[i][j],f[i-k][j-1]+g[i-k+1][i]); printf("%d\n",f[n][m]); } } -
0
0912230011 LV 8 @ 2013-10-28 14:43:49
测试数据 #0: Accepted, time = 250 ms, mem = 43480 KiB, score = 10
测试数据 #1: Accepted, time = 234 ms, mem = 43488 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 43484 KiB, score = 10
测试数据 #3: WrongAnswer, time = 265 ms, mem = 43492 KiB, score = 0
测试数据 #4: Accepted, time = 296 ms, mem = 43488 KiB, score = 10
测试数据 #5: Accepted, time = 296 ms, mem = 43520 KiB, score = 10
测试数据 #6: Accepted, time = 234 ms, mem = 43520 KiB, score = 10
测试数据 #7: Accepted, time = 812 ms, mem = 43488 KiB, score = 10
测试数据 #8: Accepted, time = 609 ms, mem = 43492 KiB, score = 10
测试数据 #9: Accepted, time = 515 ms, mem = 43488 KiB, score = 10
第三个点wa了
-
0
测试数据 #0: Accepted, time = 250 ms, mem = 43480 KiB, score = 10
测试数据 #1: Accepted, time = 234 ms, mem = 43488 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 43484 KiB, score = 10
测试数据 #3: WrongAnswer, time = 265 ms, mem = 43492 KiB, score = 0
测试数据 #4: Accepted, time = 296 ms, mem = 43488 KiB, score = 10
测试数据 #5: Accepted, time = 296 ms, mem = 43520 KiB, score = 10
测试数据 #6: Accepted, time = 234 ms, mem = 43520 KiB, score = 10
测试数据 #7: Accepted, time = 812 ms, mem = 43488 KiB, score = 10
测试数据 #8: Accepted, time = 609 ms, mem = 43492 KiB, score = 10
测试数据 #9: Accepted, time = 515 ms, mem = 43488 KiB, score = 10
-
0
program vijos1488;
var g:array[0..70,0..200]of longint;
d:array[1..200,1..200]of longint;
f:array[0..8000]of longint;
a,z:array[1..200]of longint;
i,j,k,n,m,t:longint;function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;begin
read(n,m,t);
for i:=1 to n do
read(a[i],z[i]);
for i:=1 to n-1 do
begin
fillchar(f,sizeof(f),0);
for j:=i to n do
begin
for k:=(n-i+1)*t downto a[j] do
f[k]:=max(f[k-a[j]]+z[j],f[k]);
d:=f[(j-i+1)*t];
end;
end;
for i:=1 to n do
g[1,i]:=d[1,i];
for i:=2 to m do
for j:=i to n do
for k:=i-1 to j-1 do
g:=max(g,g+d[k+1,j]);
writeln(g[m,n]);
end. -
0
做两次DP，第一次用背包解决max（表示从第i盏灯到第j盏灯的最大照明度）；第二次解决分组问题。
对于第一次DP，要降维，实践证明降维还可以降低常数，加快运行速度……├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 400ms
├ 测试数据 09：答案正确... 197ms
├ 测试数据 10：答案正确... 150ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 588ms
├ 测试数据 09：答案正确... 322ms
├ 测试数据 10：答案正确... 244ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1154ms
NO!!!
三次才AC -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 588ms
├ 测试数据 09：答案正确... 619ms
├ 测试数据 10：答案正确... 619ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1826ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 478ms
├ 测试数据 09：答案正确... 275ms
├ 测试数据 10：答案正确... 228ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：981ms预处理时出现严重错误.....
-
0
king465656 LV 8 @ 2009-01-23 15:30:27
这道题我按前辈说的做：动归+背包，但超时。哪位大牛帮我看看，指点迷津.
不胜感激。编译通过...
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 369ms
├ 测试数据 03：运行超时...
├ 测试数据 04：运行超时...
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时...
├ 测试数据 07：答案正确... 369ms
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
才20分；program P1488;
var
n,m,t,i :longint;
a :array[1..160,1..2]of longint;
ans :array[1..50,1..160]of longint;
function dp(s,d:longint):longint;
var
ff :array[0..8100]of longint;
i,j,sum :longint;
begin
sum:=(d-s+1)*t;
fillchar(ff,sizeof(ff),0);
for i:=s to d do
for j:=sum downto a do
if ff[j]ans then ans:=temp;
end;
end;
begin
assign(input,'P1488.in'); reset(input);
assign(output,'P1488.out'); rewrite(output);
readln(n,m,t);
for i:=1 to n do readln(a,a);
work;
writeln(ans[m,n]);
close(input);
close(output);
end. -
0
razhangwei LV 3 @ 2009-01-20 16:12:04
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 650ms
├ 测试数据 09：答案正确... 338ms
├ 测试数据 10：答案正确... 259ms
本来这题如果背包+动规，
背包的效率应该是n^2*v=n^2*n*m=n^3*m;
本来以为铁定超时，没想到就是这么做，无语。。。。。
Sky1231 (sky1231)
LV 10
@ 2017-07-31 14:11:11
