一次秒杀～26行

1 今早在另一道题栽过了，全部数组我都开了int64；

2 s1:=j+s[i];if s1>n then s1:=n................所以开到50就可以了

3 还可以滚动数组。。。。

4 初值要暴力点，，因为都开到int64了。。不过我写了－1，然后加if。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不用INT64，下场是悲惨的

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

郁闷～叫了4次才过的！

这个背包需要考虑一个情况。因为s[i] b[i]是longint范围的，不可能开个maxlongint*maxlongint的数组，所以开到（s+1）＊（b+1）的就行了，＋1表示超过范围的。这样用有限背包就可以AC了！

请大牛们鄙视

一开始竟然做成无限背包了，无语

血的代价，忘了10000000LL*10000000LL的LL了，结果以long存了，WA了N次

踩在前辈门的尸体上前进!!!

多谢各位前辈提醒

小弟一次AC了 !!

呵呵

尽管老朽通过了,但是我们初一的话痨病又犯了,正常人WS我,直接看下面大牛的程序.此题是经典的二维背包的变种(废话!),fi表示小狗叫的次数,j表示大狗叫的次数,即让小狗叫i次,大狗叫j次的最小费用.

一开始看上去挺简单的,其实有很多阴人的地方:

1.读入的数据应该用INT64,包括F数组也一样.

2.初值一定要大啊,我用了15个9.

3.不要信数据范围中的那个50,听我的,60直接AC..

4.不要被for i:=1..60 do

for j:=0..60 do困住(应该把i那里改为0..60)并且之后还要把f[0,0]赋值为0.

5.如果说出现小于0的情况,一定要把他赋值为0啊.

另外说一下，我是2009个提交AC的...^_^.

program tanlandegeerman;

var f:array[0..100,0..100] of int64;

n,m,s,b,x,y:int64;

si,bi,ci:array[1..1000] of int64;

max:longint;

i,j,k:longint;

function min(a,b:longint):longint;

begin

if a

除了计数变量以外都要用int64；

赋初始值f:=999999999(9个9)*999999999(9个9);

二維背包，不過需要處理的問題不少...

數據結構用二維表，F[i, j]表示讓小狗叫i聲，大狗叫j聲所需錢數。

初值F[0, 0] = 0

所求最終答案為F[s, b]

首先將F賦初值，能多大就多大，Int64扛得住...再説矩陣就60x60，内存也不會超。

優化：

1. 讀入數據優化
   
   若讀入的餅乾中，si >= s且bi >= b，則F[s, b] := Min(F[s, b], c[i]);
   
   其中c[i]為這個餅乾的價格，Min為求較小值的函數。
   
   在上述排除之外，
   
   若讀入的餅乾中，if s[i] > s then s[i] := s; if b[i] > b then b[i] := b;
   
   完成輸入數據優化。

2. 矩陣壓縮優化
   
   注意到，矩陣只能開s*b，又因爲叫聲只要大於等於要求即滿足條件，
   
   所以，假設儅我們找到一個點F[sx, bx]（sx > s或bx > b），則執行：
   
   if sx > s then sx := s; if bx > b then bx := b;
   
   再執行Min操作。
   
   當然如果既滿足sx >= s又滿足bx >= b的話，它就直接被移動到F[s, b]也就是答案的位置咯。
   
   這樣就把碩大的矩陣壓縮到了s*b的範圍内，程序也就可以承受了...

最後輸出F[s, b]的2倍值即可。

看到有人赋初值为9999999999999时,我知道我初值小了(我才100000)

这道题在艰难的改初值中ac le

核心：小于0的按0算

经典的二维背包大小求解：

一字千金：

fillchar(f,sizeof(f),最大值);

f[0,0]:=0;

for i:=1 to n do

for j:=a+60 downto 0 do

for k:=b+60 downto 0 do

begin

p:=j-w1[i];

q:=k-w2[i];

if p

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

├ 测试数据 03：答案错误...

　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

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

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

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

我就不理解了

编译通过...

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

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

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

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

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

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

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

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

Unaccepted 有效得分：70 有效耗时：0ms

如果你是这样错的，那么不要相信题目里的50,改60立刻AC

附数据范围：

const

maxx=100;

maxy=100;

var

n,ls,lb:int64;

i,j,k:longint;

s,b,c:array[1..1200]of int64;

min:int64;

f:array[0..maxx,0..maxy]of int64;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这时间…………

如果你是70分...

如果你的答案很离奇...

如果你终于想起来背包要用Int64...

如果你在读入完成后就把单价乘了2...

如果你没把读入数据的数组开到Int64...

那么...

恭喜...

.

.

.

.

.

你将继续70分...

交了4次啊！终于发现了！囧ing....

定义的时候var dp:array[0..60,1..60] of int64

赋值dp[0,0]:=max;

更不可思议的是，居然过了8个点，一直查不出来是哪错了。。。VIJ的无敌测试机。。。

program Project1;

var i,j,wf,wn,n,k,p,q:longint;

g:array[-100..1001,-100..1001]of int64;

w1,w2,v:array[0..1001]of int64;

ans:int64;

begin

readln(n,wf,wn);

for i:=1 to n do readln(w1[i],w2[i],v[i]);

for i:=0 to wf do

for j:=0 to wn do g:=999999999999999999;

g[0,0]:=0;

for k:=1 to n do

for i:=wf+100 downto 0 do

for j:=wn+100 downto 0 do

begin

p:=i-w1[k]; q:=j-w2[k];

if p