NUDT校賽 E Missile 背包dp 機率

題目

題意: 有n個目标, n種飛彈, 第i種飛彈隻能打第i個目标, 給出每種飛彈命中的機率, 每種飛彈的成本(元/個), 總價值為

總成本為

問在總價值不小于s的情況下, 最小成本是多少.

思路:

①機率問題: 假設某火箭發射k次, 全都沒命中的機率是

, 那麼命中的機率就是

, 那麼一種火箭的價值貢獻就是

, 一種火箭的成本就是

.

②考慮dp dp[i]表示目前總花費, i表示目前的最大總價值.

③遞推式: 

④初始化: 将每一個價值都置為inf, 表示要付出無窮大的花費才能達到目前價值.dp[0]=0, 0價值當然不需要花費就能達到.

⑤順序:

每種飛彈->每個價值從大到小->此種飛彈的個數.

原因: 将目前種類的飛彈的影響都考慮完,再考慮下一種飛彈.

每個價值從大到小 保證 隻用之前飛彈得到的代價 更新 目前狀态的代價. 如果從小到大更新, 因為dp數組隻有1維, 不可避免的, 就會讓已經更新過x類飛彈的低狀态影響到高狀态.我們要保證每個狀态都是由沒有此類飛彈的狀态得到, 而背包都是由低狀态得到高狀态, 是以要先枚舉高狀态(此時低狀态都是未更新的), 再更新低狀态.

另外, 最後兩維也不能反, 每種炮彈的個數隻能有一次貢獻, 而如果先枚舉個數再枚舉價值的話, 某狀态可能受到兩次不同個數飛彈的影響而改變.

⑥如果 低價值的成本>高價值的成本, 那麼 高價值的成本就可以賦給低價值的成本(因為如果小的成本就能得到大的價值, 那麼他當然能的到小的價值).

代碼:

#include<bits/stdc++.h>
#define fuck(x) std::cout<<"["<<#x<<"->"<<x<<"]"<<endl;
using namespace std;
typedef long long ll;

const int M=2e5+5;
const int inf=1e9+5;
const int mod=1e9+7;
//memset(a,0x3f,sizeof(a));
int dp[50005];
//   dp[i]=dp[ i - w[j]*(1- ( 1- p[j]) ^k) ] + v[j] *k
int n,m,s;
int w[505];
int v[505];
double p[505];
int sum=0;

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    for(int i=1; i<=n; i++) {
        scanf("%d",&v[i]);
    }
    for(int i=1; i<=n; i++) {
        scanf("%lf",&p[i]);
    }
    fill(dp,dp+50005,inf);
    dp[0]=0;
    for(int j=1; j<=n; j++) {
        for(int i=sum; i>=0; i--) {
            double tmp=1;
            for(int k=0; k<=10; k++) {
                int now=round(w[j]*(1- tmp ));
                if(i>=now)
                    dp[i]=min(dp[i],dp[ i - now   ] + v[j] * k );
                tmp=tmp*( 1- p[j]);
            }
        }
    }
    for(int i=sum; i>=0; i--) {
        dp[i]=min(dp[i],dp[i+1]);
    }
//    for(int i=0;i<505;i++){
//        printf("[%d]:%d ",i,dp[i]);
//    }
//    puts("");
    for(int i=0; i<m; i++) {
        scanf("%d",&s);
        if(dp[s]==inf) {
            printf("Impossible\n");
        } else
            printf("%d\n",dp[s]);
    }
    return 0;
}