虚拟机怎么做网站,建设网站目录,有创意的食品包装设计,胶州网站建设电话链接#xff1a;http://acdream.info/problem?pid1409 题意#xff1a;整个国家有n座城市#xff0c;每座城市有三种粉丝。 第一种一周看一场音乐剧#xff0c;挑选的音乐剧是已经在周围城市播放上演过的次数最多的音乐剧中的随机一个。 另外一种每天看一场音乐剧#xf… 链接http://acdream.info/problem?pid1409 题意整个国家有n座城市每座城市有三种粉丝。 第一种一周看一场音乐剧挑选的音乐剧是已经在周围城市播放上演过的次数最多的音乐剧中的随机一个。 另外一种每天看一场音乐剧挑选的是在本城市上映的音乐剧中的随机一个。 第三种每天看一场音乐剧挑选的是在本城市以及周围城市中上映的音乐剧中的随机一个。 周围的城市是指这座城市与当前城市之间存在路径。 我如今要带着一部音乐剧环游全国能够坐飞机不用走路径每座城市呆一周而且还存在其它m座城市在这n周内绕国上映也可能放假问我这个音乐剧所能吸引到的粉丝的总数的期望是多少。 思路首先要模拟找出每座城市每周的上映音乐剧数量。每座城市每周周围的上映的音乐剧数每一个音乐剧在每周每座城市内存在的信息数。 然后用状态压缩dp[i][j]表示第i周状态为j的条件下能吸引到的粉丝总数。 这题比較繁琐。模拟过程比較蛋疼。 代码 #include algorithm
#include cmath
#include cstdio
#include cstdlib
#include cstring
#include ctime
#include ctype.h
#include iostream
#include map
#include queue
#include set
#include stack
#include string
#include vector
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
double city[15][5];
bool vis[15][15][15];//音乐剧周城市
bool now[15][15][15];
int V[15][15];
int top[15];
int aa[15][15][15];//音乐剧,周。城市的信息数
int ans[15];
int road[15];
int Pow[15];
int cc[15][15];//周城市的上映音乐剧数
int dd[15][15];//周相邻以及本身上映的音乐剧数
double dp[15][1500];
int p[15][1500];
void init()
{Pow[0]1;for(int i1; i10; i)Pow[i]Pow[i-1]*2;return ;
}
int main()
{init();int n,m,kk,c;scanf(%d%d%d,n,m,kk);for(int i0; in; i)scanf(%lf%lf%lf,city[i][0],city[i][1],city[i][2]);for(int i1; im; i){int u,v;scanf(%d%d,u,v);V[u-1][top[u-1]]v-1;V[v-1][top[v-1]]u-1;}for(int i1; ikk; i)//剧{for(int j1; jn; j)//周{scanf(%d,c);c--;if(j!1)for(int k0; kn; k)vis[i][j][k]vis[i][j-1][k];vis[i][j][c]1;now[i][j][c]1;cc[j][c];dd[j][c];for(int k0; ktop[c]; k)dd[j][V[c][k]];}}for(int i1; ikk; i) //音乐剧for(int j1; jn; j) //周for(int k0; kn; k) //城市for(int l0; ltop[k]; l){if(vis[i][j][V[k][l]])aa[i][j][k];}int mos(1n);for(int i0; in; i)for(int j0; jmos; j)dp[i][j]-1;dp[0][0]0;for(int i1; in; i)//周{for(int j1; jmos; j)//状态{for(int k0; kn; k)//到的城市{//coutkendl;int res0;if(j-Pow[k]0)break;if(dp[i-1][j-Pow[k]]!-1){for(int l0; ltop[k]; l)if(Pow[V[k][l]]j)res;int flag 0;double tot 0;for(int l1; lkk; l){if(aa[l][i][k]resnow[l][i][k]){flag 1;break;}else if(aa[l][i][k]resnow[l][i][k])tot;}double all 0;if(flag 0)allcity[k][0]/(tot1);allcity[k][1]*7/(cc[i][k]1);allcity[k][2]*7/(dd[i][k]1);for(int ii0; iitop[k]; ii){int posV[k][ii];allcity[pos][2]*7/(dd[i][pos]1);}if(alldp[i-1][j-Pow[k]]dp[i][j]){dp[i][j]alldp[i-1][j-Pow[k]];p[i][j]k;}}}}}int nnmos-1;int way[15],ttt0;for(int in; i1; i--){//coutp[i][nn]endl;way[ttt]p[i][nn];nn-Pow[p[i][nn]];}printf(%.8lf\n,dp[n][mos-1]);for(int ittt-1;i0;i--){if(ittt-1)printf(%d,way[i]1);else printf( %d,way[i]1);}printf(\n);return 0;
}转载于:https://www.cnblogs.com/mengfanrong/p/5348274.html
