题解 P1164 【小A点菜】

FLYing · 2018-02-04 17:05:17 · 题解

本来以为又是个01板子，稍微有一点变式。

基本的思想，数组d[i]用来表示刚好能凑到体积i的方案数，于是当体积j大于当前正在做01的某件物品v[i]的时候，有：

d[j] += d[j-v[i]];

注意初始化为1。 剩下的就是个板子：

#include<cstdio>
#include<cstring>
using namespace std;
int V, N, v[105], ans, d[10005];
int max(int a, int b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d", &N, &V);
    for(int i=0; i < N; i++)
        scanf("%d", &v[i]);

    memset(d, 1, 1);

    for(int i = 0; i < N; i++)
        for(int j = V; j > 0; j--)
            if(j>=v[i])d[j]+=d[j-v[i]];

    printf("%d", d[V]);
    return 0;
}