HDU-2955 Robberies 01背包 + 概率

本文主要是介绍HDU-2955 Robberies 01背包 + 概率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

刚开始以为概率就2位小数 乘100来做WA

看了讨论区恍然大悟。

用成功逃走的概率当做价值！银行的总钱数当做背包容量！

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 106;
const int inf = 1<<30;
typedef __int64 LL;
int n,V;
float P,dp[maxn*maxn],p[maxn];
int m[maxn];
void GetDp()
{memset( dp,0,sizeof(dp) );dp[0] = 1;for( int i = 0; i < n; i ++ ){for( int j = V; j - m[i] >= 0; j -- ){dp[j] = max( dp[j],dp[j-m[i]]*p[i] );}}
}
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif  int cas;scanf("%d",&cas);while( cas -- ){scanf("%f%d",&P,&n);P = 1 - P;V = 0;for( int i = 0; i < n; i ++ ){scanf("%d%f",&m[i],&p[i]);p[i] = 1-p[i];V += m[i];}GetDp();int flag = 0;for( int i = V; i >= 0; i -- ){if( dp[i] >= P ){flag = i;break;}}printf("%d\n",flag);}return 0;
}

这篇关于HDU-2955 Robberies 01背包 + 概率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---