题目链接:校内OJ的题目,就不放链接了。
PS.可以说是本次9月月赛唯一的一道有一定难度的题目了。
题解:
考虑状压DP,假设 $sta$ 是一个二进制数,代表当前 $n$ 个人有几个是在队伍里的,剩下几个是没在队伍里的。
假设 $dp[sta][h]$:代表了当前 $sta$ 状态下,队伍最尾部那个人的位置的阴影长度为 $h$,此时整个队伍的暴躁值。
状态转移方程参见代码。
(状压DP的题解真的巨特喵难写,懒人就只能这么写写了……)
AC代码:
#include<bits/stdc++.h> using namespace std; const int maxn=17; const int INF=0x3f3f3f3f; int n; int h[maxn],a[maxn]; int dp[1<<maxn][12]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>h[i]; for(int i=1;i<=n;i++) cin>>a[i]; int edsta=(1<<n)-1; memset(dp,INF,sizeof(dp)); dp[0][0]=0; for(int sta=1;sta<=edsta;sta++) { //printf("now calc sta=%d ",sta); for(int i=1;i<=n;i++) { int k=1<<(i-1); if(sta&k) { int presta=sta-k; //printf("pre sta=%d ",presta); for(int high=0;high<=10;high++) { if(dp[presta][high]==INF) continue; if(h[i]<=high-1) { dp[sta][high-1]=min(dp[sta][high-1],dp[presta][high]); //printf("dp[%d][%d]=%d ",sta,high-1,dp[sta][high-1]); } else { if(high-1<=0) dp[sta][h[i]]=min(dp[sta][h[i]],dp[presta][high]+h[i]*a[i]); else dp[sta][h[i]]=min(dp[sta][h[i]],dp[presta][high]+(h[i]-(high-1))*a[i]); //printf("dp[%d][%d]=%d ",sta,h[i],dp[sta][h[i]]); } } } } } int ans=INF; for(int high=0;high<=10;high++) ans=min(ans,dp[edsta][high]); cout<<ans<<endl; }