洛谷 P6205 [USACO06JAN]Dollar Dayz S

题目传送门

背包,一个高精度dp

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,k;
struct kkk{
    int a[1000],len;
    kkk() {
        memset(a,0,sizeof(a));
        len = 1;
    }
}f[1001];

kkk operator +(const kkk &s,const kkk &d) {
    kkk p;int u = 0;
    int oo = max(s.len,d.len);
    for(int i = 1;i <= oo; i++) {
        p.a[i] = (s.a[i] + d.a[i] + u) % 10;
        u = (s.a[i] + d.a[i] + u) / 10;
    } 
    if(u == 1) p.a[++oo] = 1;
    p.len = oo;
    return p;
}

inline void chu() {
    for(int i = f[n].len;i >= 1; i--)
        printf("%d",f[n].a[i]);
}

int main() {
    scanf("%d%d",&n,&k);
    f[0].len = 1;
    f[0].a[1] = 1;
    for(int i = 1;i <= k; i++)
        for(int j = i;j <= n; j++)
            f[j] = f[j] + f[j-i];
    chu();
    return 0;
}