首页 > 代码库 > 男神的约会(状压dp)
男神的约会(状压dp)
有一天男神约了学姐姐去看电影，电影院有一个活动，给你一个10*10的矩阵，每一个格子上都有一个0-9的整数，表示一共十种优惠券中的一种。
观众从左上角的格子开始走，走到右下角。每走到一个有着a号优惠券的格子，都必须要玩一个a分钟的游戏来领取这张优惠券。
每次只能向右或向下走。当走到右下角的时候，如果集齐10种优惠券就可以半价看电影呢。
为了能在学姐姐面前展示自己的才智，男神准备用最少的时间领取全部的优惠券(他要省出最多的时间陪学姐姐)。聪明的你能告诉男神，他最少要花费的时间是多少？
Input
输入包含10行，每行10个数字，以空格隔开，表示格子上的优惠券的种类。数据保证存在合法路径。
Output
输出男神走到右下角的最小时间花费。
Sample Input
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5
Sample Output
50
//状态压缩dp dp[i][j][k] 到(i,j)最少花费的时间
dp[i][j][k] = max ( max ( dp[i][j-1][k] , dp[i][j-1][k&~t] ) , max ( dp[i-1][j][k] , dp[i-1][j][k&~t] ) ) + mp[i][j] ( k = (1<<mp[i][j] ) )
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define INF 0x3f3f3f3f 5 #define MX 12 6 7 int mp[MX][MX]; 8 int dp[MX][MX][(1<<10)]; // 到 (i,j) 点是 k 状态最少需要的时间 9 10 void solve()11 {12 for (int i=1;i<=10;i++)13 for (int j=1;j<=10;j++)14 {15 if (i==1&&j==1) continue;16 int t = 1<<mp[i][j];17 for (int k=0;k<(1<<10);k++)18 {19 dp[i][j][k] = min (dp[i][j][k],dp[i-1][j][k]);20 dp[i][j][k] = min (dp[i][j][k],dp[i-1][j][k&~t]);21 dp[i][j][k] = min (dp[i][j][k],dp[i][j-1][k&~t]);22 dp[i][j][k] = min (dp[i][j][k],dp[i][j-1][k]);23 dp[i][j][k]+=mp[i][j];24 }25 }26 }27 28 void Init()29 {30 memset(dp,0x3f,sizeof(dp));31 dp[1][1][(1<<mp[1][1])] = mp[1][1];32 }33 34 int main()35 {36 for (int i=1;i<=10;i++)37 for (int j=1;j<=10;j++)38 scanf("%d",&mp[i][j]);39 40 Init();41 solve();42 43 printf("%d\n",dp[10][10][1023]);44 return 0;45 }
男神的约会(状压dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。