abc270d Stones

abc270d

直接贪心每次取最大的会有问题，比如说下面的例子
11
2 4 5

我们考虑dp
\(f[i]\)表示在先手的情况下，有i个石头的局面，最多能拿多少个石头，同时记录\(g[i]\)表示选的哪一个\(a[i]\)
那么转移就是
\(f[i]=max(f[i-a[j]-a[g[i-a[j]]] ]+a[j])\)

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=2e5+5;

int n,k,cnt,s,j;
ll a[N],f[N],g[N];
int main() {
   
    // #ifdef  LOCAL
    //     freopen("in.txt","r",stdin);
    //     freopen("out.txt","w",stdout);
    // #endif

    scanf("%d %d",&n,&k);
    fo(i,1,k) scanf("%d",&a[i]);
    fo(i,0,a[1]-1) {
        f[i]=0;
        g[i]=0;
    }
    f[a[1]]=a[1];
    g[a[1]]=1;



    fo(i,a[1]+1,n) {
        fo(j,1,k){
            if (i<a[j]) continue;

            if (f[i-a[j]-a[g[i-a[j]]] ] +a[j]>f[i]) {
                f[i]=f[i-a[j]-a[g[i-a[j]]] ] +a[j];
                g[i]=j;
            }
        }
    }
    printf("%lld\n",f[n]);

    return 0;
}