[USACO 2013 Gold] No Change

作法：

首先看到 K<=16 應該可以馬上想到狀態壓縮DP。假設我們記 dp[ i ][ j ] 代表目前有有的錢幣集合為 i ，那麼買完 j ~ n 的物品最多可以剩多少錢。那麼轉移就會是枚舉每個目前可用的錢幣，並且枚舉要用這個錢幣付 j 到哪個物品的錢。但其實付到哪個物品可以不用枚舉，因為付越多當然是越好的，也就是我們只需要預處理出一個陣列 ri[ i ][ j ] ，代表「用第 i 種錢幣可以付第 j ~ ri[ i ][ j ] - 1 個物品的錢」，這顯然用雙指標在O(KN) 的時間內完成。但我們的DP陣列還是太大了，記憶體不夠。但其實只要注意到，因為我們要的只有 dp[ (1<<k)-1 ][ 1 ] 的值，而轉移的時候都會沿著 ri 陣列跳，所以其實 dp 陣列的第二維不會用到很多，也就是我們可以在第二維改成用 map 紀錄就好了。

感覺這個解蠻唬爛的，不過還好沒有TLE。( 其實用這個方法的時候，如果不先預處理好 ri 陣列，而是每次需要的時候再對前綴和陣列二分搜，就會TLE掉了QQ )

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=100000+10,maxk=16 ;
 
int k,n,s[maxn],sum[maxn] ;
 
map<int,int> d[1<<maxk] ;
vector<int> v[1<<maxk] ;
int a[maxk],tot[1<<maxk] ;
int ri[maxk][maxn] ;
int dp(int id,int S)
{
    if(id==n+1) return tot[S] ;
    auto it=d[S].find(id) ;
    if(it!=d[S].end()) return it->second ;
 
    int ret=-INF ;
    for(int i=0;i<v[S].size();i++)
    {
        int j=v[S][i] ;
        int id2=ri[j][id] ;
        if(id2>id) ret=max(ret,dp(id2,S^(1<<j))) ;
    }
    return d[S][id]=ret ;
}
 
main()
{
    freopen("nochange.in","r",stdin) ;
    freopen("nochange.out","w",stdout) ;
    scanf("%d%d",&k,&n) ;
    for(int i=0;i<k;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=n;i++) scanf("%d",&s[i]) , sum[i]=s[i]+sum[i-1] ;
 
    for(int i=0;i<(1<<k);i++) for(int j=0;j<k;j++)
        if(i&(1<<j)) v[i].push_back(j) ,
        tot[i]+=a[j] ;
 
    for(int i=0;i<k;i++) for(int j=1,j2=1,now=0;j<=n;j++)
    {
        while(j2<=n && now+s[j2]<=a[i]) now+=s[j2++] ;
        ri[i][j]=j2 ;
        now-=s[j] ;
    }
 
    int ans=dp(1,(1<<k)-1) ;
    printf("%d\n",ans<0 ? -1 : ans) ;
}