题解 - Vijos

7

PowderHan LV 10 @ 2017-05-08 12:35:07

/*
感觉以前的老题还是有的蛮好的~
数据范围n+m<=10那么我们很容易想到直接枚举每一个邮票种类
很明显容易发现根本无法枚举因为面值无上下线
那么我们给它找一个限制范围不就好了？
首先我们保证g[]为递增这样更方便
那么g[1]必然为1  不然连面额1都满足不了
这样我们就可以开始dfs
那怎么判断一种面额方案可以达到的最大连续面额呢？
我们可以用背包dp的思想
注意是完全背包(每种邮票无限多个)
即我们定义f[i]表示在当前邮票面额的安排下
组成i的面额需要的最少邮票数
所以有f[0]=0   f[i]=INF
我们用背包思想递推
对于每一个f[i]枚举每一个邮票g[j]
如果i>=g[j]   那么f[i]=min(f[i],f[i-g[j]]+1)
这个是一个很裸的背包了
注意到这个f[]一定是非降序列～
而且关于题目的要求我们发现只要递推完一个f[i]发现f[i]>n(可以贴的邮票数)
就说明到这里为止就无法达到要求了
那么就可以返回i-1了
这样我们就很容易判断一个邮票序列可以得到的连续最大值了
那么我们枚举怎么枚举下一个数？
首先我们说了必须要是递增的(否则可以被等效)
那么久从当前这个数+1开始枚举
同时对于当前求出来的这个连续最大值x
我们枚举的下一个数必然不能大于x+1
因为如果大于x+1之后必然就无法达到邮票价值x+1了
这是一个很强力的剪枝
这样的话就可以在很快的时间出结果了
注意我们要求的最终答案如果多解需要字典序更大的
因为我们是从小到大枚举
所以先得到的必然是字典序小的方案
所以更新答案的时候只要当前答案x>=ans就要更新(字典序会更大~)
这样就做完了一题啦~
还有一个细节
在dfs过程内我们很容易发现对于一个组合x1 x2 x3...
如果在后面再加上一个邮票价值(递归到下一层)
那么必然不会让解变差
所以最后的答案一定是齐全了m个的
所以*标记处加上一个cur==m也是可以得到正确答案的
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=12;
const int MAXV=505;
int Ans[MAXN],ans,ansl;
int g[MAXN];
int f[MAXV];
int n,m;

void init()
{
    cin>>n>>m;
}

int dp(int l)
{
    memset(f,0x3f,sizeof(f));   f[0]=0;
    int maxw=1;
    for(;;maxw++)
    {
        for(int i=1;i<=l;i++)
            if(maxw>=g[i])
                f[maxw]=min(f[maxw],f[maxw-g[i]]+1);
        if(f[maxw]>n)
            return maxw-1;
    }
}

void dfs(int cur)
{
    int maxw=dp(cur);
    if(maxw>=ans&&cur==m)//*
    {
        ans=maxw;   ansl=cur;
        memcpy(Ans,g,sizeof(int)*(cur+1));
    }
    if(cur==m)
        return;
    for(int i=g[cur]+1;i<=maxw+1;i++)
    {
        g[cur+1]=i;
        dfs(cur+1);
    }
}

void out()
{
    for(int i=1;i<=ansl;i++)
        cout<<Ans[i]<<" ";
    cout<<endl;
    cout<<"MAX="<<ans<<endl;
}

int main()
{
    init();
    g[1]=1; dfs(1);
    out();
}

0

ForcaBarcelibacy LV 8 @ 2017-07-18 10:57:15

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int n,k,ans=0,p[101],f[2001],tmp[201];
int dp(int dep,int sum){
memset(f,127,sizeof(f));
f[0]=0;
for (int i=1; i<=dep; i++)
for (int j=tmp[i]; j<=n*sum; j++)
f[j]=min(f[j],f[j-tmp[i]]+1);
for (int i=1; i<=n*sum; i++) if (f[i]>n) return i-1;
return n*sum;
}

void dfs(int dep,int l,int x,int sum)
{
if (dep>k)
{
if (ans<x)
{
ans=x;
for (int i=1; i<=k; i++)
p[i]=tmp[i];
}
return;
}
for (int i=l+1; i<=x+1; i++)
{
tmp[dep]=i;
int x1=dp(dep,sum+i);
dfs(dep+1,i,x1,sum+i);
}
}
int main(){
cin>>n>>k;
dfs(1,0,0,0);
for (int i=1; i<=k; i++) cout<<p[i]<<" ";
cout<<endl<<"MAX="<<ans<<endl;
return 0;
}

0

hjp_handsome LV 8 @ 2015-05-29 13:18:03

var max2,you:array[0..10]of longint;
zhi:array[0..1000]of longint;
n,m,max1:longint;

function max(now:longint):longint;
var a,s,d:longint;
begin
fillchar(zhi,sizeof(zhi),0);
for s:=1 to now do
zhi[you[s]]:=1;
a:=1;
while zhi[a]<>0 do
begin
if zhi[a]<>n then
begin
for s:=1 to now do
if ((zhi[a+you[s]]=0)or(zhi[a+you[s]]>zhi[a]+1))
then zhi[a+you[s]]:=zhi[a]+1;
end;
inc(a);
end;
exit(a-1);
end;

procedure reseach(now:longint);
var a,s,d:longint;
begin
if now<=m
then
begin
for a:=max(now-1)+1 downto you[now-1]+1 do
begin
you[now]:=a;
reseach(now+1);
end;
end
else
if max(now)>max1
then
begin
max2:=you;
max1:=max(now);
end;
end;

procedure main;
begin
readln(n,m);
fillchar(you,sizeof(you),0);
fillchar(max2,sizeof(max2),0);
you[1]:=1; max2[1]:=1; max1:=0;
reseach(2);
for n:=1 to m do
write(max2[n],' ');
writeln;
writeln('MAX=',max1);
end;

begin
main;
end.
主要问题在于确定搜索的范围，搜索范围过大很容易暴时间，所以，第K个数的取值范围是应该是第（K-1）个数+1~~~前（K-1）个数中用N{即题目给出的N}个数设计邮票的值+1

0

LN_handsome LV 9 @ 2015-05-21 14:26:40

var a,b:array[-1..11] of longint;
n,m,i,j,k,l,w:longint;
{p:array[0..1000000] of boolean;}
p:array[0..500] of longint;

procedure suan(x,y:longint);
var i,j,k,l:longint;
begin

for i:=1 to a[11] do
begin
j:=a[i];
while j<=n*a[i] do
begin
if (p[j-a[i]]+1<p[j])or(p[j]=0) then
begin
p[j]:=p[j-a[i]]+1;
end;
inc(j);
end;
end;
{for i:=0 to n do
begin
w:=w+a[x]*i;
y:=y+i;
if y<=n then p[w]:=true;
if x<a[11] then
begin
suan(x+1,y);
end;
w:=w-a[x]*i;
y:=y-i;
end; }
end;

procedure jie;
var i,j:longint;
begin
i:=0;
while (p[i+1]<=n)and(p[i+1]<>0) do
inc(i);
if i>=b[-1] then
begin
b:=a;
b[-1]:=i;
end;
end;

procedure chose(x:longint);
var i,j,k,l:longint;

function pan(y:longint):boolean;
var i,j,l:longint;
begin
pan:=false; w:=0;
fillchar(p,sizeof(p),0);
suan(1,0);
i:=0;
while (p[i+1]<=n)and(p[i+1]<>0) do
inc(i);
if y<=i+1 then
begin
a[-1]:=i;
exit(true);
end;
end;

begin

k:=0;
a[x]:=a[x-1];
while pan(a[x]+1) do
begin
inc(a[x]);
inc(a[11]);
if x=m then begin w:=0;
fillchar(p,sizeof(p),0);
suan(1,0); jie;
end;
if x<m then chose(x+1);
dec(a[11]);
end;
end;

begin

read(n,m);
a[1]:=1; a[-1]:=1; a[11]:=1;
b:=a;
b[-1]:=n;
chose(2);
for i:=1 to m do
write(b[i],' ');
writeln;
writeln('MAX=',b[-1]);

end.

一路深搜，各种搜索，本来算max也是搜索的，又来同学提醒想到了背包的思想。本来总是90分的，后来发现p数组范围当时没仔细算，就搞了个超级大的，然后改成小的就过了。。。

0

sunflower LV 9 @ 2014-08-11 19:55:27

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>

#define M 1001
#define INF 0x7fffffff

using namespace std;

int n,m;
int a[M],f[M];
int b[M];
int maxx=0;

int getmax(int x)
{
for(int i=1;i<=M;i++)
f[i]=INF;
f[0]=0;
int k;
for(int i=1;i<=M;i++)
{
for(int j=1;j<=x;j++)
if(i-a[j]>=0)
f[i]=min(f[i-a[j]]+1,f[i]);
if(f[i]>n)
{
k=i-1;
break;
}
}
return k;
}

void dfs(int num)
{
int now=getmax(num);
if(num==m)
{
if(now>maxx)
{
maxx=now;
memcpy(b,a,sizeof(a));
return ;
}
}
else
{
for(int i=now+1;i>=a[num]+1;i--)
{
a[num+1]=i;
dfs(num+1);
}
}
}

void init()
{
scanf("%d%d",&n,&m);
a[1]=1;
dfs(1);
for(int i=1;i<=m;i++)
printf("%d ",b[i]);
printf("\nMAX=%d\n",maxx);
}

int main()
{
init();
return 0;
}

0

silence_sure LV 8 @ 2012-10-15 16:25:44

DFS+DP 感觉这题目还是挺不错 NOIP的题越老越难啊通过这个题能学不少东西呢！

0

zhurui LV 8 @ 2010-03-17 22:43:07

本题存在明显的后效性：（1）如果使用递推的话在推新的一张邮票面值的时候受到前面方案的影响，前面各种方案除个别面值重合不存在共性。（2）每一次枚举一个新邮票的面值后，每一个分值的用各种邮票组成的总数也发生改变，错误就像滚雪球一样出现较大误差，这点无法写入简单的递推。

由此我们可以得到以下几点：

（1）每一次加入新邮票后对于凑成连续各种分值的邮票最小数要加以更新和记录。如果每一次只记录一个面值是否能达到，这样的记录没有什么用，因为下一次添加新邮票的时候这个面值可能因为用的邮票数太多而出现错误情况，其实这是一个简单的数学问题，并不是只要分值小，凑成这个分值的邮票数就一定更小。

（2）既然不是递推（动归），我们可以考虑搜索算法。下面来考虑一下用搜索算法的时间复杂度，这个很难给出一个稳定的多项式来表达时间复杂度，但是本题有一个细节：从一到max的所有值都要能凑到，所以我们可以每搜一步就记录一下次步的连续最大值maxc，由此可以看出有些方案搜不出k=10就已经不能再往下搜了。

我们的新邮票面值可以从上一个邮票的面值加一开始循环，因为小了可能出现两种邮票的面值搜出的是重复的，这样面值就自动排成了升序；直接循环到当前取得的连续金额的最大值加1，因为太大了就导致前后不连续，搜到这个值就可能使原来的最大值翻一翻，这已经是极限了。

程序详见我的博客：http://zhurui250.blog.163.com/blog/static/1372705202010217103927346/

0

jackalczjw LV 8 @ 2009-10-29 19:38:33

program P1179;

type

arr=array[0..2000] of byte;

var

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

f:arr;

maxa,a:array[0..100] of longint;

procedure dfs(k:integer;p:integer);

var i,j:integer;

ft:arr;

begin

if k>m then begin

if p-1>=maxp then begin

maxa:=a;

maxp:=p-1;

end;

exit;

end;

for i:=a[k-1]+1 to p do begin

a[k]:=i;

ft:=f;

for j:=i to n*i do

if (f[j-i]

0

sutank2009 LV 8 @ 2009-10-24 18:17:38

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program stamp_dp;

const

maxn=14;

maxm=502;

var

a,ans:array[1..maxn]of integer;

s:array[0..maxm]of integer;

i:integer;

n,k:integer;

max,tmax,t:longint;

function dp(kk:integer):integer;

var ii,j,min,r:integer;

begin

fillchar(s,sizeof(s),0);

for ii:=1 to maxm do

begin

min:=maxint;

for j:=1 to kk do

begin

if ii-a[j]>=0 then r:=s[ii-a[j]]+1;

if rk then break;

end;

tmax:=ii-1;

end;

procedure dps(i:integer);

var j:longint;

begin

dp(i-1);

if i>n then

begin

if tmax>=max then

begin

max:=tmax;

ans:=a;

end;

end

else

begin

for j:=a+1 to tmax+1 do

begin

a[i]:=j;

dps(i+1);

end;

end;

end;

begin

readln(k,n);

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

a[1]:=1;

dps(2);

for i:=1 to n do write(ans[i],' ');

writeln;

writeln('MAX=',max);

end.

我是一头小小小小牛……

想要快呀快，却快呀快不了^

0

vivid LV 8 @ 2009-10-12 20:23:08

打表万岁...

var

m,n:longint;

begin

readln(m,n);

if (m=1)and(n=1)then

begin

writeln('1 2');

writeln('MAX=1');

exit;

end;

if (m=1)and(n=2)then

begin

writeln('1 2');

writeln('MAX=2');

exit;

end;

if (m=1)and(n=3)then

begin

writeln('1 2 3');

writeln('MAX=3');

exit;

end;

if (m=1)and(n=4)then

begin

writeln('1 2 3 4');

writeln('MAX=4');

exit;

end;

if (m=1)and(n=5)then

begin

writeln('1 2 3 4 5');

writeln('MAX=5');

exit;

end;

if (m=1)and(n=6)then

begin

writeln('1 2 3 4 5 6');

writeln('MAX=6');

exit;

end;

if (m=1)and(n=7)then

begin

writeln('1 2 3 4 5 6 7');

writeln('MAX=7');

exit;

end;

if (m=1)and(n=8)then

begin

writeln('1 2 3 4 5 6 7 8');

writeln('MAX=8');

exit;

end;

if (m=1)and(n=9)then

begin

writeln('1 2 3 4 5 6 7 8 9');

writeln('MAX=9');

exit;

end;

if (m=2)and(n=1)then

begin

writeln('1');

writeln('MAX=2');

exit;

end;

if (m=2)and(n=2)then

begin

writeln('1 3');

writeln('MAX=4');

exit;

end;

if (m=2)and(n=3)then

begin

writeln('1 3 4');

writeln('MAX=8');

exit;

end;

if (m=2)and(n=4)then

begin

writeln('1 3 5 6');

writeln('MAX=12');

exit;

end;

if (m=2)and(n=5)then

begin

writeln('1 3 5 7 8');

writeln('MAX=16');

exit;

end;

if (m=2)and(n=6)then

begin

writeln('1 3 5 7 9 10');

writeln('MAX=20');

exit;

end;

if (m=2)and(n=7)then

begin

writeln('1 3 5 7 8 17 18');

writeln('MAX=26');

exit;

end;

if (m=2)and(n=8)then

begin

writeln('1 3 5 7 9 10 21 22');

writeln('MAX=32');

exit;

end;

if (m=3)and(n=1)then

begin

writeln('1');

writeln('MAX=3');

exit;

end;

if (m=3)and(n=2)then

begin

writeln('1 3');

writeln('MAX=7');

exit;

end;

if (m=3)and(n=3)then

begin

writeln('1 4 5');

writeln('MAX=15');

exit;

end;

if (m=3)and(n=4)then

begin

writeln('1 4 7 8');

writeln('MAX=24');

exit;

end;

if (m=3)and(n=5)then

begin

writeln('1 4 6 14 15');

writeln('MAX=36');

exit;

end;

if (m=3)and(n=6)then

begin

writeln('1 4 6 14 17 29');

writeln('MAX=52');

exit;

end;

if (m=3)and(n=7)then

begin

writeln('1 4 5 15 18 27 34');

writeln('MAX=70');

exit;

end;

if (m=4)and(n=1)then

begin

writeln('1');

writeln('MAX=4');

exit;

end;

if (m=4)and(n=2)then

begin

writeln('1 4');

writeln('MAX=10');

exit;

end;

if (m=4)and(n=3)then

begin

writeln('1 5 8');

writeln('MAX=26');

exit;

end;

if (m=4)and(n=4)then

begin

writeln('1 3 11 18');

writeln('MAX=44');

exit;

end;

if (m=4)and(n=5)then

begin

writeln('1 3 11 15 32');

writeln('MAX=70');

exit;

end;

if (m=4)and(n=6)then

begin

writeln('1 5 8 27 29 44');

writeln('MAX=108');

exit;

end;

if (m=5)and(n=1)then

begin

writeln('1');

writeln('MAX=5');

exit;

end;

if (m=5)and(n=2)then

begin

writeln('1 4');

writeln('MAX=14');

exit;

end;

if (m=5)and(n=3)then

begin

writeln('1 6 7');

writeln('MAX=35');

exit;

end;

if (m=5)and(n=4)then

begin

writeln('1 5 12 28');

writeln('MAX=71');

exit;

end;

if (m=5)and(n=5)then

begin

writeln('1 4 9 31 51');

writeln('MAX=126');

exit;

end;

if (m=6)and(n=1)then

begin

writeln('1');

writeln('MAX=6');

exit;

end;

if (m=6)and(n=2)then

begin

writeln('1 5');

writeln('MAX=18');

exit;

end;

if (m=6)and(n=3)then

begin

writeln('1 7 12');

writeln('MAX=52');

exit;

end;

if (m=6)and(n=4)then

begin

writeln('1 4 19 33');

writeln('MAX=114');

exit;

end;

if (m=7)and(n=1)then

begin

writeln('1');

writeln('MAX=7');

exit;

end;

if (m=7)and(n=2)then

begin

writeln('1 5');

writeln('MAX=23');

exit;

end;

if (m=7)and(n=3)then

begin

writeln('1 8 13');

writeln('MAX=69');

exit;

end;

if (m=8)and(n=1)then

begin

writeln('1');

writeln('MAX=8');

exit;

end;

if (m=8)and(n=2)then

begin

writeln('1 6');

writeln('MAX=28');

exit;

end;

if (m=9)and(n=1)then

begin

writeln('1');

writeln('MAX=9');

exit;

end;

if (m=10)and(n=4)then

begin

writeln('1 6 41 67');

writeln('MAX=427');

exit;

end;

if (m=7)and(n=4)then

begin

writeln('1 5 24 37');

writeln('MAX=165');

exit;

end;

if (m=10)and(n=3)then

begin

writeln('1 10 26');

writeln('MAX=146');

exit;

end;

end.

0

SDreaming LV 10 @ 2009-09-23 11:07:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

额。参考noip2007提高组初赛完善2

0

m^^m LV 10 @ 2009-09-21 20:02:00

第六组是：10 4

第七组是：2 7！！！！答案不唯一！！！500为上限！！！

0

yzl609271536 LV 10 @ 2009-09-05 20:33:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

N,M 搞反了交了4次

0

fjxmlhx LV 10 @ 2009-09-05 15:19:27

这题超范围。有一个点N=10,M=4。

这题很赞，涉及到了DFS过程中动归数组的维护。让我想起CEOI第二题。

令dp[i][j]表示前I种邮票，凑到J至少要多少张邮票。

然后DFS方案，每次暴搜当前位放什么，放的上界是已经放的值所能组成的最大连续值+1.回溯时维护DP数组即可。

0

lc123456 LV 8 @ 2009-08-28 10:32:21

第6个点过不了的

把数组开到2000 试试

0

SecretAgent LV 10 @ 2009-08-28 01:06:20

DFS+递推

07年提高组最后一题的程序完善就是这个

那里说的很清楚了.

关键是对k的连续状态最少所需的邮票数记录

刚交上去时216错误wa掉第6个点,后来干脆把上界改到3000就AC了..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

xusc_2009 LV 9 @ 2009-08-05 15:12:11

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

程序总算ac，思路参见了Noip2007初赛卷

42行，程序还比较漂亮。

一开始做的时候用的是每次dfs枚举，再用背包算出当前可达到的最大值

严重超时

然后惊异于那初赛卷的程序奇快（9个点）

仔细一读，发现如果记录达到某数所用的邮票数，则运算量大大减少。

于是又花了20分钟自己写了一遍，ac……

我花了一早上自己瞎编都没成果，下午睡醒一下子就过了……

正所谓吾尝终日而思矣，不如须臾之所学也

0

没13 LV 8 @ 2009-08-01 14:46:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

太牛的题拉， DP+dfs，我喜欢，多重背包，帅

0

freefly LV 10 @ 2009-07-31 22:09:57

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

wzc1995 LV 10 @ 2009-07-23 15:44:14

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

又学会了一种算法

#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

题解

132 条题解

邮票面值设计

信息

状态

开发

支持

题解

132 条题解

邮票面值设计

信息

状态

开发

支持

还没有账户？

登录