# 26 条题解

• @ 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]);
}
}
``````
• @ 2017-07-31 14:11:35

很H2O的題

• @ 2017-08-20 21:44:29

@sky1231: %%%大佬

• @ 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了

• @ 2013-10-28 14:43:23

测试数据 #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

• @ 2009-11-03 20:34:00

题目描述好粗心！

不贴了。。。

• @ 2009-10-24 20:46:39

Accepted 有效得分：100 有效耗时：1122ms

诧异了，用了最弱智的背包方法.....第一遍sunny，90分光荣超时，可是题目显示Accepted.....然后再交一次，居然还是sunny，心想完了，然后突然变成Conan，AC.....

方法和lx差不多.......

• @ 2009-10-23 20:26:26

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

for i:=1 to n do

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.

• @ 2009-09-26 11:59:37

数据可能比较弱吧

g可以预先处理出来的，表示从i到j的在合理的情况下的最大照明

这步用n*n*（最大照明）的复杂度

接着用n*n*m的复杂度求解

注意边界！！

• @ 2009-09-04 22:33:58

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 72ms

• @ 2009-08-06 21:55:39

var

i,j,m,n,t,k:longint;

a,z:array [1..160] of integer;

b:array [0..8000] of longint;

s:array [1..160,1..160] of longint;

f:array [0..160,0..50] of longint;

function max(x,y:longint):longint;

begin

if x

• @ 2009-08-02 08:40:26

555555555哇啊啊,不活啦!三次AC,有一次是提交失误,多打了些东西..555应该两次AC的..AC率啊..139题纪念,没什么好说的.主要是预处理部分的优化,可以考虑容量更改为t*(n-i+1)这样,就可以将原先的四重循环变为三重循环，可以加速,并且，一定要用一维背包.最后.DP分组的部分,可以考虑乘积最大的方法.

• @ 2009-07-11 16:51:07

300/488(61%)纪念

• @ 2009-05-28 11:16:09

做两次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

• @ 2009-04-18 17:11:50

不容易啊~~~~~~~~~~~~~~~~

这题看上去很简单，就是DP，但是居然交了3次…………它怎么连个输入格式都不给。

另：装箱也可以预处理，不一定要背包

• @ 2009-03-22 15:25:49

编译通过...

├ 测试数据 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

• @ 2009-03-13 13:31:15

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 588ms

├ 测试数据 09：答案正确... 619ms

├ 测试数据 10：答案正确... 619ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1826ms

• @ 2009-01-23 20:50:20

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 478ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：981ms

预处理时出现严重错误.....

• @ 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);

for i:=1 to n do readln(a,a);

work;

writeln(ans[m,n]);

close(input);

close(output);

end.

• @ 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;

本来以为铁定超时，没想到就是这么做，无语。。。。。

• @ 2008-12-20 19:46:50

真倒霉……

一开始重复计算，60；

后来是因为二维背包，90……

最后改成一维，才AC……

• @ 2008-12-15 00:16:46

第十个人

终于可以去睡觉了0：15

我的艰难AC路

0，70，70.......AC

原因160*50我当成是3000

结果交了n多次

思路不烦就是细节烦人

ID
1488

7

(无)

813

171

21%

1