SGU---104 DP
题目链接:
https://cn.vjudge.net/problem/SGU-104
题目大意:
假设你想以最美观的方式布置花店的橱窗,你有F束花,每束花的品种都不一样,同时,你至少有同样数量的花瓶,被按顺序摆成一行。花瓶的位置是固定的,并从 左至右,从1至V顺序编号,V是花瓶的数目,编号为1的花瓶在最左边,编号为V的花瓶在最右边。花束则可以移动,并且每束花用1至F的整数唯一标识。标识 花束的整数决定了花束在花瓶中排列的顺序,即如果i<j,则花束i必须放在花束j左边的花瓶中。
例如,假设社鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有的花束在放入花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边 的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空置,每个花瓶中只能放一柬花。
每一个花瓶的形状和颜色也不相同,因此,当各个花瓶中放入不同的花束时,会产生不同的美学效果,并以美学值(一个整数)来表示。空置花瓶的美学值为零。在上述例子中,花瓶与花束的不同搭配所具有的美学值,可以用下面式样的表格来表示。
花瓶 |
||||||
1 |
2 |
3 |
4 |
5 |
||
花束 |
1.杜鹃花 |
7 |
23 |
-5 |
-24 |
16 |
2.秋海棠 |
5 |
21 |
-4 |
10 |
23 |
|
3.康乃馨 |
-21 |
5 |
-4 |
-20 |
20 |
例如,根据上表,社鹃花放在花瓶2中,会显得非常好看;但若放在花瓶4中则显得很难看。
为取得最佳美学效果,你必须在保持花束顺序的前提下,使花束的摆放取得最大的美学值,如果具有最大美学值的摆放方式不止一种,则其中任何一种摆放方式都可以接受,但你只可输出其中一种摆放方式。
假设条件(Asumption)
1≤F≤100,其中F为花束的数量,花束编号从1至F.
F≤V≤100,其中V是花瓶的数量。
-50≤Aij≤50,其中Aij小是花束i在花瓶j中时的美学值。
输入(Input)
输入文件是正文文件(text file),文件名是flower.inp。
第一行包含两个数:F,V
随后的F行中,每行包含V个整数,Aij即为输入文件中第(I+1)行中的第j个数。
输出(Input)
输出文件必须是名为f1ower.out的正文文件,文件应包含两行:
第一行是程序所产生摆放方式的美学值。
第二行必须用F个数表示摆放方式,即该行的第k个数表示花束K所在的花瓶的编号。
解题思路:
dp[i][j]=max(dp[i-1][k]+f[i][j])//注意k要从i-1开始枚举!!!
路径更新,注意DP数组初始化为-INF
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m;
const int maxn = ;
int Map[maxn][maxn];
int dp[maxn][maxn], path[maxn][maxn];
int main()
{
cin >> n >> m;
memset(dp, -INF, sizeof(dp));
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
cin >> Map[i][j];
}
}
dp[][] = ;
for(int i = ; i <= n; i++)
{
for(int j = i; j <= m; j++)//dp[i][j] = max(dp[i - 1][k] + Map[i][j])
{
for(int k = i - ; k < j; k++)
{
if(dp[i][j] < dp[i - ][k] + Map[i][j])
{
dp[i][j] = dp[i - ][k] + Map[i][j];
path[i][j] = k;//记录路径
}
}
//cout<<dp[i][j]<<" "<<path[i][j]<<" "<<i<<" "<<j<<endl;
}
}
int ans = -INF, ansy;
for(int i = n; i <= m; i++)
{
if(ans < dp[n][i])
{
ans = dp[n][i];
ansy = i;
}
}
cout<<ans<<endl;
stack<int>q;
int t = n;
while(ansy)
{
q.push(ansy);
ansy = path[t--][ansy];
}
while(!q.empty())
{
printf("%d", q.top());
q.pop();
if(!q.empty())printf(" ");
else printf("\n");
}
return ;
}
最新文章
- 使用SuperSlide 实现标签切换
- CSS-border属性制作小三角
- SplashTop Remote + 4核android平板 试用
- 关于AutoComplete整合
- poj 2531 Network Saboteur( dfs )
- 测试Kettle在增量更新的时候是否支持级联——不支持(基于mysql)
- Spring4.0学习笔记(6) —— 通过工厂方法配置Bean
- Android Studio ---------------- 软件使用小细节(更新中。。。。。。)
- last reboot
- Http的操作(不传递参数)
- C#整理
- QUIC简要
- yii2 中布局文件的 设置方法
- NO.1-M2
- Pie
- C 语言内存区域分配(进程的各个段)详解
- VS的工作目录和输出目录
- js获取当前页面url网址信息
- TreeTagger
- Change事件多参
热门文章
- Dev中自带添加、编辑、删除等按钮的文字颜色等修改
- C# BBcode 转 Markdown
- Spring-全局异常拦截
- Spring Boot + MyBatis + Druid + Redis + Thymeleaf 整合小结
- Golang 模板
- 关于pycharm 打不开某些文件夹和文件打不开的问题
- [h5+api]移动app开发用到的微信好友,朋友圈,qq好友,新浪微博分享合集
- node.js(http协议)
- ubuntu中获取文件名称并生成txt文件
- 132.1.001 Union-Find | 并查集