当前位置: 代码迷 >> 综合 >> HDU4815Little Tiger vs. Deep Monkey(01背包)
  详细解决方案

HDU4815Little Tiger vs. Deep Monkey(01背包)

热度:65   发布时间:2023-12-06 19:30:16.0

题意:

给出N道题,和一个概率P,然后给出每道题对应的得分x(每道题只有两个选项,一个正确一个错误)。两个人来答题,一个人是随机选择答案,问另一个人至少要答多少分才能保证有P的概率不会失败。


思路:

01背包,最大分数为40000,01背包处理,记录这40000个分数出现的次数然后从小分数遍历一边即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 40005;
ll dp[maxn], v[45];
int main()
{ll t, n;double p;scanf("%d", &t);while(t--){scanf("%I64d%lf", &n, &p);memset(dp, 0, sizeof(dp));ll sum = 0;for(int i = 1; i <= n; i++){scanf("%I64d", &v[i]);sum += v[i];}dp[0] = 1;for(int i = 1; i <= n; i++)for(int j = sum; j >= v[i]; j--)dp[j] += dp[j-v[i]];ll tmp = 1LL << n;sum = 0;for(int i = 0; i <= 40000; i++){sum += dp[i];if(sum*1.0/tmp >= p){printf("%d\n", i);break;}}}return 0;
}

概率DP写法:


d[i][j],表示前i道题,得分为j的概率 。 这样,最终打完所有题目之后猴子得任意分数的概率我们就知道了,老虎要想赢就要至少

得和他一样的分数,那么就很好办了,从0~max分,不断相加概率,当概率大于P时的分数就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 50;
const double INF = 10000000.0;
int T,n,a[maxn];
double p,d[50][40000+100];
int main()
{scanf("%d",&T);while(T--){scanf("%d%lf",&n,&p);ll sum = 0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);sum += a[i];}memset(d,0,sizeof(d));d[0][0] = 1.0;for(int i=1; i<=n; i++){for(int j=0; j<=sum; j++){if(j >= a[i]) d[i][j] += d[i-1][j-a[i]]/2;d[i][j] += d[i-1][j]/2;}}int ans;double pp = 0.0;for(int i=0; i<=sum; i++){pp += d[n][i];if(pp > p || fabs(pp-p) < 1e-6){ans = i ;break;}}printf("%d\n",ans);}return 0;
}


  相关解决方案