一开始是把n个课程看成一个区间，在这个区间上做m个划分，然后发现，这区间划分TMD写完不就是没有2进制优化的分组背包吗？我2了...

二进制优化也可以的

program p1198;

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

t,z:array[1..21]of longint;

f:array[0..21,0..201]of int64;

w:array[1..21,0..201]of int64;

begin

readln(m,n);

for i:=1 to n do

readln(t[i],z[i]);

for i:=1 to n do w:=t[i];

for i:=1 to n do

for j:=2 to m do

begin

w:=w;

for k:=1 to z[i] do

begin

w:=w div (j-1);

w:=w*j;

end;

end;

for i:=1 to m do f[0,i]:=maxlongint div 2;

f[0,0]:=0;

for i:=1 to n do

for j:=1 to m do

begin

f:=maxlongint div 2;

for k:=0 to j do

if f+w

至于动规吗？

#include

long a[21],b[21];

long long pd[21];

long long mi(long d,long m){

int i;

long long ans;

if(d==0)

return 0;

ans=1;

for(i=1;i

初始化要开得很大

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最朴素的分组背包，秒杀。（实在是懒得写二进制表示的那种分组）。

唯一注意的是：要开int64;

Matrix67神牛喜欢简洁，不喜欢高精度；

#include

using namespace std;

ifstream fin("a.in");

ofstream fout("a.out");

int n,m,cost[30][300]={0},f[30][300]={0};

int p(int x,int y)

{

int s=1;

for(int i=1;i>n>>m;

for(i=0;i>b;

for(j=1;j

用dfs或者dp都可以

但dfs只能过3个点

把每件物品按取的数量拆成n个分成一组，

然后就是分组背包的方法

边界条件比较头疼啊

还有就是要用int64

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

囧，把

交了3次才过

原因:没用int64

为什么偶觉得这题要高精度，，，，，，code被我编猥琐掉了，，勉强a掉。。。。。。。。。

f=min{f+c}

为什么放到动规，贪心一下就搞定了

每次选一个最少增长的，每次m种决策

复杂度 nm

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

额 我竟把TEMP类型写成LONGINT了！！一次AC没了~

庆祝一下自己70AC

var a,b:array[0..20] of longint;

f,c:array[0..20,0..200] of real;

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

min:real;

begin

readln(n,m);

for i:=1 to m do

begin

readln(a[i],b[i]);

for j:=1 to n do

begin

c:=a[i];

for k:=1 to b[i] do

c:=c*j;

end;

end;

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

for i:=1 to n do

f[1,i]:=c[1,i];

for i:=2 to m do

for j:=1 to n do

begin

min:=32000000000000;

for k:=0 to j do

begin

if f+c

f:=min{f+w};

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

dangdang~~第一次一写完过了样例就来交了。。。果然不是天才，wa了两个点。。。再改改。。。嘿嘿

看一看楼下的，果然体会到了那种感觉。。。有的题目我做的要死要活，别人却大叫农夫山泉。。。这道题我半个小时搞定，却有人贴老长的程序求解。。。风水轮流转

怎么用完全背包，他可是求最小价值啊，初始化也是个问题

提交了3次....

第一次：预处理k打成i 10分

第二次：被m=1阴了... 90分

第三次:AC

看了各位牛的讲解，明白了一个道理，这题可以用分组背包- -！

另外又想到一个，貌似可以用完全背包。。

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

编译通过...

├ 测试数据 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,m,i,j,k:longint;map,f:array[0..21,0..201]of int64;

a,b:array[0..20]of longint;

min:int64;

function pmx(i,j:Longint):int64;

var z:int64;k:longint;

begin

if j=0 then exit(0);

z:=1;

for k:=1 to b[i] do

begin

z:=z*j;

end;

z:=z*a[i];

exit(z);

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(a[i],b[i]);

end;

fillchar(map,sizeof(map),0);

for i:=1 to m do

for j:=0 to n do

begin

map:=pmx(i,j);

end;

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

for j:=1 to n do

begin

f[1,j]:=map[1,j];

end;

for i:=2 to m-1 do

for j:=0 to n do

for k:=0 to j do

begin

if (f=0)or(f+map

var a,b,i,j,k,n,m:integer;

c:array[1..20,1..200] of int64; {预处理数组}

f:array[0..200] of int64;

begin

readln(n,m);

for k:=1 to m do begin

readln(a,b);

for i:=1 to n do begin

c[k,i]:=a;

for j:=1 to b do

c[k,i]:=c[k,i]*i;

end;

end;

f[0]:=0;

for i:=1 to n do

f[i]:=100000000000000000;

for k:=1 to m do

for i:=n-1 downto 0 do

for j:=1 to n-i do

if f[i]+c[k,j]