hdu 1203 - I NEED A OFFER!

我不是女神ヾ 2022-07-12 06:11 129阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1203][http_acm.hdu.edu.cn_showproblem.php_pid_1203]

# 定位 #

*  动态规划
 *  0-1背包问题变形
 *  相互独立事件概率计算

# 分析 #

*  存储需求由整数变为浮点数, 规模为 0≤m,n≤10000, 对存储的要求更严格了, 进行空间优化, 规避风险。
 *  相互独立事件概率计算
    
    事件A、B相互独立, 事件发生的概率分别为 PA、PB, A、B均不发生的概率为1−(1−PA)(1−PB)。

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_N 10001
    
    int cost[MAX_N];
    float value[MAX_N];
    float dp[MAX_N];
    
    int main()
    {
        int m,n;
        int i,j;
        scanf("%d*c",&n);
        scanf("%d*c",&m);
        while(!(n == 0 && m == 0))
        {
            memset(cost,0,sizeof(cost));
            memset(value,0,sizeof(value));
            memset(dp,0,sizeof(dp));
            for(i=1;i<=m;i++)
            {
                scanf("%d*c",&cost[i]);
                scanf("%f*c",&value[i]);
            }
            for(i=cost[1];i<=n;i++)
            {
                dp[i] = value[1];
            }
            for(i=2;i<=m;i++)
            {
                for(j=n;j>=cost[i];j--)
                {
                    dp[j] = 1 - (1 - dp[j-cost[i]]) * (1 - value[i]) > dp[j] ? 1 - (1 - dp[j-cost[i]]) * (1 - value[i]) : dp[j];
                }
            }
            printf("%.1f%%\n",dp[n]*100);
            scanf("%d*c",&n);
            scanf("%d*c",&m);
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">15MS</td> 
   <td align="center">1564K</td> 
   <td align="center">933B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

Ver 2.0 2017-2-18

[http_acm.hdu.edu.cn_showproblem.php_pid_1203]: http://acm.hdu.edu.cn/showproblem.php?pid=1203