方格取数(1)
Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4702Accepted Submission(s): 1782
Problem Description 给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input 包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output 对于每个测试实例，输出可能取得的最大的和
Sample Input
3 75 15 21 75 15 28 34 70 5
Sample Output
188
入门压缩dp，与 Poj - 3254 Corn Fields类似。
【Hdu-1565 方格取数(1) （状态压缩dp入门题】用dp[i][j]表示前i行，第i行选第j种状态时的最优解，
首先找出所有本行不冲突的状态（即这一行中没有相邻的情况），存入state数组
计算出第i行取第j种状态时可得到的数值stn[i][j]
那么dp[i][j]=max{dp[i][j],dp[i-1][k]+stn[i][j]} (k表示第i-1行取第k种状态
最终答案即为dp[n][j]中的最大值。
代码：
#include
#include
#include
using namespace std;
const int hpn=18000;
int state[hpn],stn[25][hpn],dp[25][hpn];
//dp[i][j]:前i行，第i行选第j种状态时的最优解
int mst,map[25][25];
//第i行选第j种状态时的值inline int bet(int x,int y)
{
if(x>y) return x;
return y;
}void find_all_state(int n)
{
memset(state,0,sizeof(state));
mst=0;
//最多有多少种状态
int lin=(1<>n)
{
if(n==0)
{
cout<<0<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)