LGP3092题解

看 DP 的时候翻到的题，发现这题的坑鸽子了一年半

这个状态感觉比较厉害，还是来记录一下吧。

首先硬币数量很少让我们想到状压，可以想出来一个十分 navie 的状态：\(dp[S][n]\) 表示用过 \(S\) 这些硬币，走到 \(n\) 的最少花费。

转移也是十分暴力，但是不可能通过此题。

不可能继续考虑状态数量过高的做法，所以考虑 \(O(n)\) 的状态或者 \(O(2^k)\) 甚至 \(O(k2^k)\) 的状态。

我也不知道这个状态是怎么想出来的。。。觉得非常厉害（或者说我太菜了）

设 \(f[S]\) 为使用了这些金币能走的最远的位置。于是可以枚举一个子集进行转移，加一个二分就能够做到 \(O(2^k\log n)\)。

#include<cstdio>

typedef long long ll;

const int M=1<<16;

int n,k,m[20],dp[M],sum[100005];

ll ans=1e18,num,f[M];

inline ll min(const ll&a,const ll&b){

    return a>b?b:a;

}

inline int BS(int id,int M){

	int L=id,R=n,mid,ans=id;

	while(L<=R)if(sum[mid=L+R>>1]-sum[id-1]<=M)ans=mid,L=mid+1;else R=mid-1;

	return ans;

}

signed main(){

    int i,j,x,id;

    scanf("%d%d",&k,&n);

    for(i=0;i^k;++i)scanf("%d",m+i),num+=m[i];

    for(i=1;i<=n;++i)scanf("%d",sum+i),sum[i]+=sum[i-1];

    for(i=0;i^1<<k;++i){

        for(j=0;j^k;++j)if(i>>j&1){

            x=i^1<<j;

            if((id=BS(dp[x]+1,m[j]))>dp[i]){

                dp[i]=id;f[i]=f[x]+m[j];

                if(dp[i]==n&&f[i]<ans)ans=f[i];

            }

        }

    }

    printf("%lld",ans==1e18?-1:num-ans);

}

巴特西

LGP3092题解

最新文章

热门文章