J - 男神的约会
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
有一天男神约了学姐姐去看电影,电影院有一个活动,给你一个10*10的矩阵,每一个格子上都有一个0-9的整数,表示一共十种优惠券中的一种。
观众从左上角的格子开始走,走到右下角。每走到一个有着a号优惠券的格子,都必须要玩一个a分钟的游戏来领取这张优惠券。
每次只能向右或向下走。当走到右下角的时候,如果集齐10种优惠券就可以半价看电影呢。
为了能在学姐姐面前展示自己的才智,男神准备用最少的时间领取全部的优惠券(他要省出最多的时间陪学姐姐)。聪明的你能告诉男神,他最少要花费的时间是多少?
Input
输入包含10行,每行10个数字,以空格隔开,表示格子上的优惠券的种类。数据保证存在合法路径。
Output
输出男神走到右下角的最小时间花费。
Sample input and output
0 1 2 3 4 5 6 7 8 9 | 50 |
影响当前决策的有所在的位置和收集过的优惠劵因此定义状态dp[i][j][sta]为到i,j位置sta状态的最小花费,问题来了,sta怎么表示,比较好的办法是用一个二进制,一位对应一种优惠劵,0表示没有收集过,1表示收集过。状态转移方程dp[i][j][st|1<<mp[i][j]]=min(dp[i-1][j][st],dp[i][j-1][st]|(i-1,j)+mp[i][j],(i,j-1)合法,st相等),注意递推顺序应该是由左上角往右下斜着推,用一个队列来实现。
memset是按字节赋值的,so。int只有赋值-1和0才会对应-1和0
#include<cstdio>
#include<memory.h>
#include<queue>
#include<algorithm>
using namespace std; const int MAXSTA=0x3ff;
const int MAXij=;
//const int SIGN=16843009;//0x01010101
int dp[MAXij][MAXij][MAXSTA]; int mp[MAXij][MAXij];
bool vis[MAXij][MAXij][MAXSTA];
int solve()
{
queue<int>qi;
queue<int>qj;
queue<int>qst;
int ci=,cj=,cst=<<mp[][];
memset(dp,,sizeof(dp));
//memset(vis,0,sizeof(vis));
dp[ci][cj][cst]=mp[][]; int ni,nj,nst;
do
{
if(ci<){
ni=ci+,nj=cj;
nst=cst|(<<mp[ni][nj]);
dp[ni][nj][nst]=min(dp[ni][nj][nst],dp[ci][cj][cst]+mp[ni][nj]);
if(!vis[ni][nj][nst])
{
qi.push(ni);
qj.push(nj);
qst.push(nst);
vis[ni][nj][nst]=true;
}
}
if(cj<){
ni=ci,nj=cj+;
nst=cst|(<<mp[ni][nj]);
dp[ni][nj][nst]=min(dp[ni][nj][nst],dp[ci][cj][cst]+mp[ni][nj]);
if(!vis[ni][nj][nst])
{
qi.push(ni);
qj.push(nj);
qst.push(nst);
vis[ni][nj][nst]=true;
}
}
ci=qi.front();
cj=qj.front();
cst=qst.front();
qi.pop();
qj.pop();
qst.pop();
}while(qi.size());
} int main()
{
//freopen("Jinput.txt","r",stdin);
int i,j;
for(i=;i<;i++)
for(j=;j<;j++)
scanf("%d",&mp[i][j]); solve();
printf("%d",dp[][][MAXSTA]);
}