P1616 疯狂的采药

发表于 更新于 分类于 本文字数： 152 阅读时长 ≈ 1 分钟

dp，注意数组索引(⁎⁍̴̛͂▿⁍̴̛͂⁎)✲ﾟ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#define scan(x) scanf("%lld",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define pn(x,y) printf("###%lld:::%lld\n",x,y)
using namespace std;
typedef long long LL;
const LL N=1e4+1;
LL a[N],b[N],m,t,r[10000001],min1=1e8;
LL dyp(LL x) {
    if(x<min1||r[x])return r[x];
    LL q=0;
    f(i,0,m-1) {
        if(a[i]<=x) {
            q=q<b[i]+dyp(x-a[i])?b[i]+dyp(x-a[i]):q;
        }
    }
    r[x]=q;
    //pn(x,q);
    return q;
}

int main() {
    scan(t);
    scan(m);
    f(i,1,m) {
        scan(a[i-1]);
        min1=min1<a[i-1]?min1:a[i-1];
        scan(b[i-1]);
    }
    //pn(t,m);
    f(i,1,t) {
        dyp(i);
    }
    printf("%lld",dyp(t));
    return 0;
}