状态压缩dp,利用2进制位数以及或运算保存获得的优惠券的张数。

可知当前格子[i,j]只与格子[i-1, j]、格子[i, j-1]有关,所以得状态方程如下:

状态方程:

dp[i][j][k|1<<data[i][j]]=min(dp[i][j][k], min(dp[i][j-1][k], dp[i-1][j][k])+data[i][j]);


题目地址:http://acm.uestc.edu.cn/#/problem/show/1134


代码:

StatusAccepted
Time1ms
Memory1548kB
Length765
LangC++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define memset(a,b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
const int inf=0x3f3f3f3f;
const int maxn=12;
const int n=10;
int data[maxn][maxn], dp[maxn][maxn][1<<10];
int main()
{
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            scanf("%d", &data[i][j]);
        }
    }
    memset(dp, INF);
    dp[1][1][1<<data[1][1]]=data[1][1];
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            if(i==1&&j==1)continue;
            for(int k=0;k<=1023;k++){
                dp[i][j][k|1<<data[i][j]]=min(dp[i][j][k], min(dp[i][j-1][k], dp[i-1][j][k])+data[i][j]);
            }
        }
    }
    printf("%d\n", dp[10][10][1023]);
    return 0;
}