UESTC_男神的约会 2015 UESTC Training for Dynamic Programming

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

Sample Input Sample Output
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
50

解题思路:

我们考虑f( i , j , k) ->在格子 i , j 且 身上票的集合是 k 时所需的最小花费.

因为必须观看,所以转移代价是O(2) 的.

注意边界条件和最终票没满时,这些状态是不合法的.

#include <iostream>
#include <cstring>
#include <cstdio> using namespace std;
const int maxn = + ;
int f[maxn][maxn][<<],g[maxn][maxn];
int dir[][] = {,,,}; inline bool inmap(int x,int y)
{
return x < && x >= && y < && y >= ;
} int dp(int x,int y,int val)
{
if (f[x][y][val] != -)
return f[x][y][val];
int num = g[x][y];
int &ans = f[x][y][val] = << ;
if (!inmap(x,y))
{
if ( ((x == && y == ) || (x == && y== ) || (x == && y == )) && val == ( << ) -)
return ans = ;
else
return ans = << ;
}
for(int i = ; i < ; ++ i)
{
int newx = x + dir[i][];
int newy = y + dir[i][];
ans = min(ans,dp(newx,newy,val | ( << num)) + num); // Must Play
}
return ans;
} int main(int argc,char *argv[])
{
memset(f,-,sizeof(f));
for(int i = ; i < ; ++ i)
for(int j = ; j < ; ++ j)
scanf("%d",&g[i][j]);
cout << dp(,,) << endl;
return ;
}
上一篇:Discuz3.4-SSRF-从触发点到构造payload


下一篇:HDU 4417 (划分树+区间小于k统计)