P1317 开心的金明

Published on 2009 / 10 / 21

我很郁闷，这样的0/1背包变种问题我原来一起刷的时候怎么没做。又得重新写代码。懒惰的我啊。

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

#include<stdio.h>

long N,M,V[25],P[25],Re[26][30001];

long Fun(long thing,long money)
{
    if(thing==M)
        return 0;
    if(Re[thing][money]==0)
    {
        long a,b;a=0;
        if(money>=V[thing])
            a=Fun(thing+1,money-V[thing])+P[thing]*V[thing];
        b=Fun(thing+1,money);
        Re[thing][money]=a>b?a:b;
    }
    return Re[thing][money];
}

int main()
{
    scanf("%ld %ld",&N,&M);
    long a,b;
    for(a=0;a<M;a++)
        scanf("%ld %ld",&V[a],&P[a]);
    b=Fun(0,N);
    printf("%ld\n",b);
    return 0;
}