acdream 1409 Musical 狀壓DP

鏈接：http://acdream.info/problem?

pid=1409

題意：整個國家有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 i=1; i<=10; 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 i=0; i<n; i++)scanf("%lf%lf%lf",&city[i][0],&city[i][1],&city[i][2]);for(int i=1; i<=m; 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 i=1; i<=kk; i++)//劇{for(int j=1; j<=n; j++)//周{scanf("%d",&c);c--;if(j!=1)for(int k=0; k<n; 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 k=0; k<top[c]; k++)dd[j][V[c][k]]++;}}for(int i=1; i<=kk; i++) //音樂劇for(int j=1; j<=n; j++) //周for(int k=0; k<n; k++) //城市for(int l=0; l<top[k]; l++){if(vis[i][j][V[k][l]])aa[i][j][k]++;}int mos=(1<<n);for(int i=0; i<=n; i++)for(int j=0; j<mos; j++)dp[i][j]=-1;dp[0][0]=0;for(int i=1; i<=n; i++)//周{for(int j=1; j<mos; j++)//狀態{for(int k=0; k<n; k++)//到的城市{//cout<<k<<endl;int res=0;if(j-Pow[k]<0)break;if(dp[i-1][j-Pow[k]]!=-1){for(int l=0; l<top[k]; l++)if(Pow[V[k][l]]&j)res++;int flag = 0;double tot = 0;for(int l=1; l<=kk; l++){if(aa[l][i][k]>res&&now[l][i][k]){flag = 1;break;}else if(aa[l][i][k]==res&&now[l][i][k])tot++;}double all = 0;if(flag == 0)all+=city[k][0]/(tot+1);all+=city[k][1]*7/(cc[i][k]+1);all+=city[k][2]*7/(dd[i][k]+1);for(int ii=0; ii<top[k]; ii++){int pos=V[k][ii];all+=city[pos][2]*7/(dd[i][pos]+1);}if(all+dp[i-1][j-Pow[k]]>dp[i][j]){dp[i][j]=all+dp[i-1][j-Pow[k]];p[i][j]=k;}}}}}int nn=mos-1;int way[15],ttt=0;for(int i=n; i>=1; i--){//cout<<p[i][nn]<<endl;way[ttt++]=p[i][nn];nn-=Pow[p[i][nn]];}printf("%.8lf\n",dp[n][mos-1]);for(int i=ttt-1;i>=0;i--){if(i==ttt-1)printf("%d",way[i]+1);else printf(" %d",way[i]+1);}printf("\n");return 0;
}