博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
luogu P1854 花店橱窗布置
阅读量:4843 次
发布时间:2019-06-11

本文共 1100 字,大约阅读时间需要 3 分钟。

依旧是一道dp

大概是那天在讲dp?

数据范围依旧良心

dp[i][j]表示前i个花瓶里放j朵花的最大价值

转移方程

dp[i][j]=max(dp[i][j],dp[j+k-1][j-1]+a[j][j+k])

第j朵花放哪枚举一下,取最大值

还有一点就是观赏价值可能为负所以要赋初值为负极大

code

#include
#include
using namespace std;#define N 110int a[N][N];int dp[N][N];void print(int i,int j) { if(j == 0) return ; for(int k = 0; k <= i - j; k++) if(dp[i][j] == dp[j + k - 1][j - 1] + a[j][j + k]) { print(j + k - 1,j - 1); printf("%d ",j + k); break; }}int main() { int f,v; scanf("%d%d",&f,&v); for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) scanf("%d",&a[i][j]); for(int i = 1; i <= f; i++) dp[i][i] = dp[i - 1][i - 1] + a[i][i]; for(int i = 1; i <= v; i++) for(int j = 1; j <= f; j++) { dp[i][j] = -1*0x3f3f3f3f; for(int k = 0; k <= i - j; k++) dp[i][j] = max(dp[i][j],dp[j + k - 1][j - 1] + a[j][j + k]); } printf("%d\n",dp[v][f]); print(v,f); return 0;}

写着写着就饿了(x【大雾

想吃狗粮(?

 

转载于:https://www.cnblogs.com/sevenyuanluo/p/10380749.html

你可能感兴趣的文章
Solr添加paoding分词器
查看>>
charles 抓包 (一)
查看>>
隐藏电池栏,遮罩层
查看>>
ES6学习之Iterator和For...of循环
查看>>
css 在各种浏览器兼容调整
查看>>
三元环、四元环计数
查看>>
SpringBoot
查看>>
【mark】linux查看端口占用
查看>>
String的trim()用于去掉字符串前后的空格
查看>>
jquery相关代码
查看>>
USACO 2.3 Zero Sum
查看>>
android 工具类 DateUtil
查看>>
EM算法原理
查看>>
高速排序算法
查看>>
EJB究竟是什么,真的那么神奇吗??
查看>>
数据结构——集合有关
查看>>
NSCondition
查看>>
常用单词7
查看>>
html5中input的type类型有哪些(总结)
查看>>
(转)dp动态规划分类详解
查看>>