luogu 1437 敲砖块(DP)
2024-10-14 19:17:25
这道题的DP的状态设计的很有想法啊。
假如我们一行一行来选择的话,状态将会极其复杂。
如果一列一列来看的话,比如你想选aij,那么第i列的前j个都要选,并且第i+1列的前j-1个都要选。
于是状态就很好设计了,定义dp[n][i][j]表示还剩下n个要选的砖块,当前选择第i列的前j个所能达到的最大分值。
那么dp[n][i][j]=max(dp[n-j][i+1][k]+sum[i][j])(j-1<=k<=n-i).
记忆化搜索一下就OK了。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int a[N][N], sum[N][N], dp[N*N][N][N], n; int dfs(int x, int col, int row){
if (x<||(col>n&&x)) return -INF;
if (~dp[x][col][row]) return dp[x][col][row];
if (x==) return row==?:-INF;
int res=-INF;
FOR(i,max(,row-),min(x,n-col)) res=max(res,dfs(x-row,col+,i)+sum[col][row]);
return dp[x][col][row]=res;
}
int main ()
{
int m, ans=;
scanf("%d%d",&n,&m); mem(dp,-);
FOR(i,,n) FOR(j,,n-i+) scanf("%d",&a[i][j]), sum[j][i]=sum[j][i-]+a[i][j];
FOR(i,,n) ans=max(ans,dfs(m,,i));
printf("%d\n",ans);
return ;
}
最新文章
- Java-jdbc操作数据库
- 使用Python scipy linprog 线性规划求最大值或最小值(使用Python学习数学建模笔记)
- Android 利用SurfaceView进行图形绘制
- 基于PHP生成静态页的实现方法
- Linux字符串替换一例:根据IP地址获取指定内容
- 增加字体和颜色样式-------CSS
- Codeforces Round #336 (Div. 2) D. Zuma
- C++ 类中指向函数的指针 以及 类模板
- Bootstrap入门(七)组件1:字体图标
- 》》HTML5 移动页面自适应手机屏幕四类方法
- 史上最最靠谱,又双叒叒简单的基于MSXML的XML解析指南-C++
- [C++]PAT乙级1012.数字分类 (20/20)
- Centos7+hadoop2.7.3+jdk1.8
- [Luogu 3401] 洛谷树
- linux下安装zabbix服务器
- AIX 补丁升级
- Spring Security 与 OAuth2 介绍
- WebSockets Tutorial(教程一)WebSockets简介
- Javascript 思维导图 绘制基础内容(值得一看)
- C#客户端(WinForm)开机自动启动实现
热门文章
- 20155318 《Java程序设计》实验四 (Android程序设计)实验报告
- 2016-2017-2 20155339 《Java面向对象程序设计》实验三敏捷开发与XP实践实验报告
- P,NP,NPC的通俗解释
- linux 同步 rsync的使用——远程服务器同步配置
- Android 测试 之MonkeyRunner
- springmvc传参---LocalDateTime、Date等时间类型转换
- TW实习日记:第八天
- ConcurrentHashMap(JDK1.8)为什么要放弃Segment
- 排查GCC 4.4.X版本优化switch-enum的BUG
- 【RL系列】马尔可夫决策过程——Gambler&#39;s Problem