#include

#include

using namespace std;

int n,m;

int a[ 15 ];

int ans[ 15 ];

int Max;

int DP( int l){

int f[ 1000 ];

f[ 0 ] = 0 ;

f[ 1 ] = 1 ;

int i = 1 ;

while (f[i] f[i - a[j]] + 1 )

f[i] = f[i - a[j]] + 1 ;

if (f[i] == n + 1 ) return i - 1 ;

}

return i;

}

void dfs( int k){

if (k == m){

int tmp = DP(k);

if (tmp >= Max){

Max = tmp;

memcpy(ans,a, sizeof ( int ) * 15 );

}

}

else {

int tmp = DP(k) + 1 ;

for ( int i = a[k] + 1 ;i

move 很好用啊。

因为这道题要不断给数组赋值，用move最大的点0.4s过，而用循环或赋值语句需要1.2s

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

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

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

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

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

├ 测试数据 06：运行时错误...| 错误号: 103 | 文件未打开

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

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

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

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

103错误怎么回事？

第六个数据是7 4吗？为什么我机子上测的好好的

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢各位大牛，又学会了一种新方法

楼下的楼下：我在自己机子上测7 4，答案和你一样

但我交上去还是AC了，WHY？

难道是你测试数据弄错了？

后枚举到的方案如果与已知最优解一样也更新，即用>=，这点从题上看不出

DFS+DP

栈记录所用邮票的面值

每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1

然后DP，记录达到每个面值用的最少邮票数，不断更新最优解

第1张邮票的面值肯定为1，所以从第二张开始搜索即可。

第六个数据是 7 4

我的输出是

1 5 24 37

MAX=165

可vijos是1 6...

各位高手，我哪儿错了？？？？

你们的输出是什么？？？

小弟我快疯了！！

我的搜索过程：

try(dep,pre,now);

begin

if dep=m+1 then {更新 exit}

for i:=pre+1 to now+1 do

{a[dep]:=i; dp(dep,j); //算出dep深度的max值，放在j里面

try(dep+1,i,j); }

end;

或者把你们正确的程序这组数据答案贴上来，让我检查一下！ 小弟感激不尽！

楼下，不会把，那哪位把你们的程序贴上来看看！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

交了十次，一直错或超，后来把背包上界卡在５００，竟然全０ＭＳ

太恶心了，交了3道才过，后面两次程序一模一样的…………

DP+搜索就过了，第一次数组开小了…………

很无奈的，在两组大数据面前，交了表，感觉程序已经优化了很多。。。莫非是C实在很慢？。。。

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

编译通过...

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

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

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

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

　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

第四个是怎么搞的？？

标准： 1 4

错误: MAX=....

附我的程序

program stamps;

var n,k,ans:longint;

f:array[0..1000000]of longint;

a,show:array[0..40]of longint;

procedure enter;

begin

readln(n,k);

a[1]:=1;

ans:=0;

end;

function work(p:longint):longint;

var i,j,max:longint;

begin

f[0]:=0; max:=a[p]*n;

for j:=1 to max+1 do begin

f[j]:=n+1;

for i:=1 to p do

if (j>=a[i]) and (f[j-a[i]]+1n then break;

end;

if j>=ans

then begin

ans:=j-1; show:=a;

end;

end;

procedure otry(v:longint);

var i,j,min,max:longint;

begin

if v>k

then begin

if a[k]*n>ans

then work(k);

exit;

end;

min:=a[v-1]+1; max:=work(v-1)+1;

for i:=min to max do begin

a[v]:=i;

otry(v+1);

end;

end;

procedure print;

var i:longint;

begin

for i:=1 to k do write(show[i],' '); writeln;

writeln('MAX=',ans);

end;

begin

enter;

otry(2);

print;

end.

有谁能告诉我怎么错的吗？

第6组数据是：

7 4

我输出结果跟07年提高组初赛最后标程输出的一样为什么我错的。。

我输出是：

1 5 24 37

MAX=165

而VIJOS的答案却是1 6...

怎么回是？我已经用>=了，记录的是后面的

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DFS+DP才是王道

同楼下，第七组如果有相同的就需要更新

注意数据范围，最好用integer，不要用longint(不过我用的longint)

还有要注意的是MAX要大写，否则WA就不愿别人了

跟鹰牛一样 被第七组给折磨了n次

透露一下下 第七组数据 :n=2 m=7

有两种方案 但是要求面值尽量取大一点

所以更新的时候 如果生成的方案跟现有的最优方案一样 就更新一次

我骗了一下数据才知道的

谁要其他组的数据可以问我要(希望管理员不要封我号！)

编译通过...

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

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

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

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

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

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

　├ 错误行输出

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

　├ 错误行输出

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

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

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

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

Unaccepted 有效得分：80 有效耗时：291ms

6: 标准行输出：1 6 ...

错误行输出：MAX=...

7：标准行输出：1 3 ...

错误行输出：MAX=...

为什么啊？

const NN=20;

maxint=30000;

maxl=500;

var bestx,x:array [0..NN] of integer;

y:array [0..maxl] of integer;

j,n,m,maxvalue:integer;

procedure result;

var i:integer;

begin

for i:=1 to m do write(bestx[i],' ');

writeln;

writeln('MAX=',maxvalue);

end;

procedure backtrace(i,r:integer);

var j,k:integer;

z: array[0..maxl] of integer;

begin

for j:=0 to x*(n-1) do

if (y[j]

此题较简单但我提交了n多次,原因我认为m>n直接让m:=n,我觉着多了没用,因此输出少了很多.20分钟写完了因为这句话调了2多小时 -_-|| 郁闷啊.

怨念终结……

真够郁闷

交了n次后发现

数组开小了

=.=

我居然以为答案不超过 100 呢...