题解 - Vijos

0

yc0576 LV 8 @ 2012-07-26 00:15:46

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

直接裸背包就可以过。stl的set小数据有优势，

大数据的时候，基本上10000个点每个都访问了。

所以直接变成10000*lg10000=4倍时间

然后stl速度大家懂的，就会T了。

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int n;

int dp[100][11004];

int dd[104][104];

int cnt[10004];

int sum;

void solve(){

int tv;

int pos;

sum = 0;

memset(dp,0,sizeof(dp));

memset(cnt,0,sizeof(cnt));

for (int i = 0; i < n; i++)

{

dp[i][0] = 1;

for (int j = 1; j = 0; k--)

if (dp[i][k])

dp[i][k + dd[i][j]] = 1;

}

for (int j = 0; j

0

nevets LV 7 @ 2012-07-21 18:44:19

这题很坑爹。。直接100个背包就行了**不用担心超复杂度**。。另外注意一定不要用vector记录数据。。不然会超时！最好在线做。。记录所有城堡最小值貌似对时间优化不是很大。。

0

xiegengsheng LV 7 @ 2010-07-08 08:41:29

var

a,b:array[0..10000]of 0..1;

i,j,k,n,m:integer;

begin

read(n);

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

fillchar(b,sizeof(b),0); b[0]:=1; read(m);

while m-1 do

begin

for j:=10000-m downto 0 do

if b[j]=1 then b[j+m]:=1;

read(m);

end;

for j:=0 to 10000 do

if b[j]=0 then a[j]:=0

else if i=1 then a[j]:=1;

end;

k:=0;

for i:=1 to 10000 do

if a[i]=1 then k:=i;

write(k);

end.

0

F.u LV 8 @ 2010-07-06 17:35:35

本该很简单的背包问题。却 WA 了几次

var

b:Array[1..100,0..10000] of boolean;

n,i,j,max,maxx,x:longint;

begin

readln(n);

for i:=1 to n do

begin

read(x); max:=0; b[i][0]:=true;

while x-1 do

begin

for j:=x+max downto x do

if b[i][j-x] then b[i][j]:=true ;

max:=x+max; read(x)

end;

if max>maxx then maxx:=max

end;

for i:=maxx downto 0 do

begin

for j:=1 to n do

if not b[j][i] then break;

if not b[j][i] then continue;

break

end;

writeln(i)

end.

0

zouxiang LV 8 @ 2010-04-09 20:59:12

优化前：

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

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

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

Unaccepted 有效得分：90 有效耗时：1303ms

优化后：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

。。。其实就是背包吧。

0

junhui LV 7 @ 2010-04-04 14:12:11

var

f:array[1..100,0..10000] of integer;

i,max,k,smax,p,n,x:integer;

begin

readln(n);

fillchar(f,sizeof(f),0);

for i:=1 to n do begin

max:=0;

f:=1;

while true do begin

read(x);

if x=-1 then break;

for k:=max downto 0 do begin

if f=1 then begin

f:=1;

if k+x>max then max:=k+x;

end;

end;

end;

if smax

0

hjc5484855 LV 8 @ 2010-03-18 21:16:59

still，你a数组的第二维要开大，要到10000，才不会201

0

still LV 5 @ 2010-03-17 16:36:42

能帮我看看为什么有几组答案错误呢

var

a:array[1..100,0..500]of boolean;

b:array[1..100]of longint;

x,y,i,k,n,m,max,max1,p:longint;

begin

readln(n);

for x:=1 to n do

begin

k:=1;

repeat

read(b[k]);

if b[k]=-1 then readln else

begin

max:=max+b[k];

a[x,b[k]]:=true;

m:=k;y:=b[k];

if m1 then

begin

for i:=1 to m-1 do

begin

inc(k);

b[k]:=y+b[i];

a[x,b[k]]:=true;

end;

end;

inc(k);

if b[k]=-1 then b[k]:=0;

end;

until b[k]=-1;

if max>max1 then max1:=max;

max:=0;

end;y:=0;

for i:=1 to 100 do a:=true;

while (max1>0)and(p=0) do

begin

for i:=1 to n do

if a=false then y:=1;

if y=0 then

begin

write(max1);

p:=1;

end

else

dec(max1);y:=0;

end;

if max1=0 then write('0');

end.

0

273942569 LV 7 @ 2010-03-03 14:14:16

设F[J]为长度为J的积木的个数,令F[J]=N 解即为 J

做法:

1.每一组积木均算出可达到的高度HIGHT(产生高度)

2.map表示能否达到长度为I的积木(记录)

同时记录达到高度为I的组数即 INC(F);(注意判断本组是否有2个达到I高度的解)

3.计算出最大高度MAXHIGHT

4.输出自己想-_-

第一次写题解请多多包涵0.0

0

lichao LV 8 @ 2010-03-02 20:46:10

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

速度还挺快..

#include

#include

using namespace std;

int n,k,i,j,ma;

bool g[10010],f[10010];

int main()

{

/*freopen("p1059.in","r",stdin);

freopen("p1059.out","w",stdout);*/

scanf("%d",&n);memset(g,true,sizeof(g));

for(i=1;ima) ma=j+k;

}

}

for(j=0;j=0;i--)

if (g[i])

{

printf("%d\n",i);

return 0;

}

}

0

laijingtao LV 8 @ 2009-11-11 23:02:24

弱弱的问一句

for j:=h downto 0 do

if (f[j]=1) and (f[j+k]=0) then

begin

f[j+k]:=1;inc(g[j+k]);

end;

改成

for j:=k to h do

if (f[j-k]=1) and (f[j]=0) then

begin

f[j]:=1;inc(g[j]);

end;

为什么不对？

0

aaaaa11111 LV 9 @ 2009-11-09 12:16:44

2星纪念

0

qq726902291 LV 4 @ 2009-11-07 16:16:55

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

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

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

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

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

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

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

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

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

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

水

0

5244372 LV 4 @ 2009-11-07 11:16:09

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

悲剧啊！！！！！！！！！

终于通过了，今天是RP爆发。一定要去买彩票，中几个亿回来。。。。。。。。。

0

strini LV 8 @ 2009-11-04 18:05:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|_

不是很好看,不过经过优化后的双层dp居然一次Ac了.

题解:

嵌套动态规划,外层动态规划解决这样的问题,前i层保持高度j是否能做到,即0或1。则f[i][j] = f[j] 且j能够由第i座塔的积木构成。判断积木构成依靠内层动态规划。g[x][i][j]表示前i块积木是否能构成长度j，x表示第x座塔。g[x][i][j] = min{ g[x][j], g[x][i][j-a[x][i]]}; 由于空间需求比较大，考虑使用滚动数组，并将内存动态规划作为预处理进行。

0

小弟不才 LV 8 @ 2009-11-04 11:17:49

哎，有点失落，没秒杀

0

sinbking11 LV 8 @ 2009-11-04 10:39:48

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：运行超时|无输出...

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

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

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

Unaccepted 有效得分：90 有效耗时：34ms

program jimu;

var i,j,k,n,x,high,max:longint;

f:array[0..15000]of boolean;

a:array[1..15000]of integer;

begin

readln(n);

f[0]:=true;

for k:=1 to n do

begin

read(x);

high:=0;

while (x-1) do

begin

inc(high,x);

for i:=high downto 0 do

if not(f) and (f[i]) then

begin

f[x+i]:=true;

inc(a[x+i]);

end;

read(x);

end;

if max

0

他在那里 LV 7 @ 2009-11-01 09:16:04

就是判定性的背包问题

0

june_fiend LV 8 @ 2009-10-31 17:27:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

郁闷没秒杀。本菜惭愧in

0

liuyibin LV 7 @ 2009-10-29 22:01:04

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

var

n,min,m,i,j,k,x,con:integer;

count:array[1..100]of integer;

h:array[1..100,1..100]of integer;

f:array[1..100,0..100,0..6000]of boolean;

kai,kk:boolean;

begin

readln(n);

min:=maxint;

for i:=1 to n do

begin

read(x);

con:=0;

m:=0;

while x-1 do

begin

inc(con);

h:=x;

f:=true;

m:=m+x;

read(x);

end;

if m

题解

265 条题解

积木城堡

信息

状态

开发

支持

题解

265 条题解

积木城堡

信息

状态

开发

支持

还没有账户？

登录