http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3502
题目大意就是要做n道题目,顺序不定,每一题的AC概率和之前做过的题目有关,给出一张概率表。最后要求给出一个字典排序最小的
题目序列使得AC题目的数量的期望最大。
n道题一共有2^n种状态,dp[i]表示第i中状态下的最大期望。假设i=10111那么dp[i]如何更新呢,显然dp[i]和dp[j]有关,其中
j=00111,10011,10101,10110,dp[j]的状态分别加上第5,3,2,1道题所对应的期望值就是dp[i]所对应的所有状态,取最大的一种更新即可。
这道题还要注意的就是浮点数的比较大小的问题。当dp[i]-q和0比较时,应该设一个精度误差EPS,然后比较:
dp[i]-q=0对应fabs(dp[i]-q)<EPS
dp[i]-q>0对应dp[i]-q>EPS
dp[i]-q<0对应dp[i]-q<EPS
代码如下:
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const double EPS=1e-8;
const int MAXN=12;
double p[MAXN][MAXN];
double dp[1<<MAXN];
string pre[1<<MAXN];
int n,cases;
double q;
int main()
{
freopen("e:\\zoj\\zoj_3502.txt","r",stdin);
cin>>cases;
while(cases--)
{
cin>>n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%lf",&p[i][j]);
dp[0]=0;
pre[0]="";
for(int k=1;k<(1<<n);++k)
{
dp[k]=-1;
for(int i=0;i<n;++i)
{
if(k&(1<<i))
{
q=0;
for(int j=0;j<n;++j)
{
if(k&(1<<j))
{
q=max(q,p[j][i]);
}
}
q=dp[k^(1<<i)]+q/100;
if((q>dp[k]+EPS)||(q>dp[k]-EPS&&pre[k^(1<<i)]<=pre[k]))
{
dp[k]=q;
pre[k]=pre[k^(1<<i)];
pre[k]+=('A'+i);
}
}
}
}
printf("%.2f\n%s\n", dp[(1 << n) - 1], pre[(1 << n) - 1].c_str());
//printf("%.2lf\n",dp[(1<<n)-1]);
//cout<<pre[(1<<n)-1]<<endl;
}
return 0;
}
分享到:
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
一个非常非常非常非常实用的zoj结题代码
zoj的代码实现,很好,而且很全面,全部实现。
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 3502 Contest.md
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
能AC 通过的c++代码,包括zoj1002,1091,1789
浙江大学zoj题目代码,大量水题代码,齐全