https://www.luogu.org/problemnew/show/P2473

一句话题意:有n种宝物,捡起会有得分(可能为负),有k轮可以捡起宝物.其中有些宝物,需要另外的宝物捡起过才能捡起.

问采取最优策略的期望得分.

 

解:期望的最大特点在于难写的递推式和倒序DP

但这道题没那么恶心,递推式还是挺好写的(指看完题解之后可以自己写出DP式子)

f[i][S]表示在第1轮到第i-1轮内宝物是否取过的状态为S，第i轮到第K轮的最大期望得分

f [ i ][ S ] 在S满足时可以取或不取 f[ i ][ S ] =max( f[ i + 1 ] [ S ] ,  f [ i+1 ][ S | (1<<(j-1))] + a[j])

不满足时只可以不拿即f[i][S]=f[i+1]

中间的各个状态要在什么时候除以n有点恶心,要好好想想.

下配AC代码:

 

#include
     
      using namespace std ;const int MAXN=300;int K,n,a[30],b[30];double dp[105][33000];int main(){    scanf("%d%d",&K,&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        while(1){            int tra1=0;            scanf("%d",&tra1);            if(!tra1) break;            else b[i]=b[i]|(1<<(tra1-1));        }    }//    for(int i=1;i<=n;i++){//        cout<
      
       <
       
        =1;i--){
   //diao luo ci shu        for(int j=0;j < (1<
       
      
     

TAG : SIN_XIII