首页 > 其他分享 >P4329 [COCI2006-2007#1] Bond

P4329 [COCI2006-2007#1] Bond

时间:2024-04-05 15:33:24浏览次数:25  
标签:25 int max COCI2006 P4329 00110 2007 dp

原题链接

题解

二进制dp
etc: 令 \(dp[00110]\) 代表前两个任务选23两个人出战的最大成功率 则 \(dp[00110]=max(dp[00010]+a[3][2],dp[00100]+a[2][3])\)

code

#include<bits/stdc++.h>
using namespace std;
double a[25][25]={0};
double dp[1<<22]={0};
int cal(int now)
{
    int sum=0;
    while(now)
    {
        sum+=now%2;
        now/=2;
    }
    return sum;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            a[i][j]/=100.0;
        }
    }

    dp[0]=1;

    for(int i=1;i<(1<<n);i++)
    {
        int num=cal(i);

        for(int j=0;j<n;j++)
        {
            if((i>>j)&1) dp[i]=max(dp[i],dp[i^(1<<j)]*a[j+1][num]);
        }
    }

    printf("%.6lf\n",dp[(1<<n)-1]*100.00);
    return 0;
}

标签:25,int,max,COCI2006,P4329,00110,2007,dp
From: https://www.cnblogs.com/pure4knowledge/p/18115790

相关文章

  • P3622 [APIO2007] 动物园 -题解
    好写爱写没事干所以有了这篇题解洛谷P3622[APIO2007]动物园题解$Link$hzoi题库洛谷题目说的挺繁琐,其实就传达了一个很简单的信息:\(n\)个动物,\(c\)个小孩,每个小孩能看到\(5\)个动物(所在的位置)\(E\)到\(E+4\),有\(F\)个害怕的动物,\(L\)个喜欢的动物。如果视野中有至......
  • PROG2007编程II
    PROG2007编程II总结职称评定2类型投资组合到期日4月8日星期一下午11:59AEST/AEDT(第6周开始)长度NA权重60%看法单元学习结果此评估任务映射到以下ULO:ULO2:用面向对象编程语言设计、实现、测试和调试简单程序。ULO3:演示如何使用类机制来支持封装和高效的代码。ULO4:分析并确定适当......
  • 「NOI2007」社交网络
    floyd#最短路floyd维护最短路和方案即可因为floyd的本质是一个每次加入一个点的dp,所以这样的统计是不会重复计算的//Author:xiaruize#ifndefONLINE_JUDGEboolstart_of_memory_use;#else#definedebug(x)#endif#include<bits/stdc++.h>usingnamespacestd;#......
  • 2007 年考研英语真题 - 阅读 1 解析
    2007 年考研英语真题-阅读1解析Ifyouweretoexaminethebirthcertificatesofeverysoccerplayerin2006'sWorldCuptournament,youwouldmostlikelyfindanoteworthyquirk:elitesoccerplayersaremorelikelytohavebeenbornintheearliermonths......
  • 2007 年考研英语真题 - 阅读 3 解析
    2007年考研英语真题-阅读3解析Duringthepastgeneration,theAmericanmiddle-classfamilythatoncecouldcountonhardworkandfairplaytokeepitselffinanciallysecurehasbeentransformedbyeconomicriskandnewrealities.[1]          ......
  • 2007 年考研英语真题 - 阅读 2 解析
    2007年考研英语真题-阅读2解析Forthepastseveralyears,theSundaynewspapersupplementParadehasfeaturedacolumncalled"AskMarilyn".[1] 翻译:在过去的几年,《星期日报》的副刊《游行》开设了一个名为 “询问玛丽莲” 的专栏。1.Forthepastseveral......
  • 2007 年考研英语真题 - 新题型解析
    2007 年考研英语真题 - 新题型解析HowCanaParentHelp?[1]                 翻译:家长如何提供帮助?Mothersandfatherscandoalottoensureasafelandinginearlyadulthoodfortheirkids.[2]      翻译:为确保孩子成年早期有一个安......
  • 2007 年考研英语真题 - 阅读 4 解析
    2007 年考研英语真题 - 阅读 4 解析Itneverrainsbutitpours.[1]  翻译:祸不单行。1.Itneverrainsbutitpours. 基本含义是:不雨则已,一雨倾盆;主要指事情(尤其是坏事), 不来则已,一来就接二连三地来(祸不单行);也有含义是:不鸣则已,一鸣惊人。Justasbossesandboa......
  • 2007 年考研英语真题 - 翻译题解析
    2007 年考研英语真题 - 翻译题解析ThestudyoflawhasbeenrecognizedforcenturiesasabasicintellectualdisciplineinEuropeanuniversities.[1]                  翻译:几个世纪以来,欧洲的各所大学一直认为法学学习是一门基础知识学科。1.......
  • [HAOI2007][洛谷P2218]覆盖问题
    看到这道题,思考一下后发现要用二分答案。所以为什么要用二分?因为标签有二分还在二分专题里因为对于\(ans\)来说,如果\(ans\)不行,那么\(ans-1\)也一定不行;也就是说,答案满足单调性,所以可以二分;也是因为暴力明显过不了那么对于平面上的一些点来说,如果我们用一个最小的矩形......