codevs1358棋盘游戏(状压dp)

关键词：

/*
三维状压dp 转移的时候分步即可
棋盘只需要放0~9个数字,所以最多只有111111111这样的的状态
输出别忘减一(减一才是111111111) 
*/

#include<cstdio>
#include<cstring>

#define maxn 1500

using namespace std;
int g[12][12],f[12][12][maxn],ans;

int min(int x,int y){return x<y?x:y;}

int main()
{
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++)
            scanf("%d",&g[i][j]);
    memset(f,127/3,sizeof(f));
    f[1][1][1<<g[1][1]]=g[1][1];
    int mxx=1<<10,SS;
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++)
            for(int S=0;S<mxx;S++){
                SS=S|(1<<g[i+1][j]);
                f[i+1][j][SS]=min(f[i+1][j][SS],f[i][j][S]+g[i+1][j]);
                SS=S|(1<<g[i][j+1]);
                f[i][j+1][SS]=min(f[i][j+1][SS],f[i][j][S]+g[i][j+1]);
            }
    printf("%d
",f[10][10][mxx-1]);
    return 0; 
}

[codevs1050]棋盘染色2（状态压缩dp）

   题目大意：有一个5*N(≤100)的棋盘，棋盘中的一些格子已经被染成了黑色，求最少对多少格子染色，所有的黑色能连成一块。   这题卡了我1h，写了2.6k的代码，清明作业一坨还没做啊。。。之前一直以为... 查看详情

codevs——2853方格游戏（棋盘dp）

 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 题目描述 Description菜菜看到了一个游戏，叫做方格游戏~游戏规则是这样的：在一个n*n的格子中，在每个1*1的格子里都能获得一定数量的积分奖励，记左上... 查看详情

codevs2853方格游戏--棋盘dp(代码片段)

方格游戏：http://codevs.cn/problem/2853/ 这和传纸条和noip方格取数这两个题有一定的相似性，当第一眼看到的时候我们就会想到设计$dp[i][j][k][l]$(i,j表示一个人走到i行j个点，而另一个人走到k行第l个点)这么一个状态。转移方程当... 查看详情

codevs2594解药还是毒药(状压dp)

2594解药还是毒药  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond  题目描述 DescriptionSmart研制出对付各种症状的解药，可是他一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治... 查看详情

codevs2800送外卖（状压dp）

题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），... 查看详情

codevs2596售货员的难题(状压dp)

2596售货员的难题  时间限制:1s 空间限制:32000KB 题目等级:钻石Diamond  题目描述 Description某乡有n个村庄(1<n<＝15)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且... 查看详情

codevs——1169传纸条（棋盘dp）

2008年NOIP全国联赛提高组 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中... 查看详情

bzoj4676xor-mul棋盘拆位+状压dp

【BZOJ4676】Xor-Mul棋盘Description一个n*m的棋盘，左上角为(1,1),右下角为(n,m)。相邻的2点之间有连边（如下图中实线）特殊地，(1,i)与(n,i)也连有一条边（如下图中虚线）,i=1..m。如下图，就是一个n=3,m=4的棋盘。每个点(i,j)给定2个值a[i]... 查看详情

状压dp总结(代码片段)

...时，达到节约空间的目的。题型一、冲突问题1.1特殊方格棋盘题目描述分析我们设f[i][j]为当前的状态为(i)，放置到第(j)行时的方案数但是，因为我们要在(n imesn)的棋盘上放置(n)个车，所以，我们必定要在每一行都放置一个车因... 查看详情

[cometoj#3b]棋盘_状压dp

棋盘题目链接：https://cometoj.com/contest/38/problem/B?problem_id=1535数据范围：略。题解：因为行数特别小，所以$dp$的时候可以状压起来。之后就非常傻逼了....代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm&g... 查看详情

sgu131状压dp

棋盘覆盖（二）时间限制：1000 ms | 内存限制：65535 KB  描述ThebanquethallofComputerScientists‘PalacehasarectangularformofthesizeMxN(1<=M<=9,1<=N<=9).Itisnecessarytolayhardwoodflo 查看详情

codevs1085数字游戏（环形dp+划分dp）

1085数字游戏  时间限制:1s 空间限制:128000KB 题目等级:黄金Gold  题目描述 Description丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得... 查看详情

dp--状压dp(代码片段)

ProblemDescription互不侵犯在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。Analysisofideas把每一行的每一个状态用一个... 查看详情

bzoj1087状压dp

...  Solved:2390[Submit][Status][Discuss]Description　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附 查看详情

洛谷2774方格取数问题|状压dp

题目描述在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出... 查看详情

51nod1327棋盘游戏(代码片段)

远古大坑神仙DP状态设计题https://blog.csdn.net/white_elephant/article/details/83592103从行的角度入手，无论如何都要状压每列最多放一个，所以从列的角度入手每列会左端点结束，右端点出现，以及空位个数设为：l[i],r[i],md[i]直接决定当前... 查看详情

poj2411mondriaan'sdream(状压dp)

题意：给出一个n*m的棋盘，及一个小的矩形1*2，问用这个小的矩形将这个大的棋盘覆盖有多少种方法。析：对第（i，j）位置，要么不放，要么竖着放，要么横着放，如果竖着放，我们记第（i，j）位置为0，（i+1，j）为1，如果... 查看详情

bzoj1087题解状压dp

1087:[SCOI2005]互不侵犯KingTimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 3112  Solved: 1816[Submit][Status][Discuss]Description　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方 查看详情