当前位置:网站首页>Usaco3.4 "broken Gong rock" band raucous rockers - DP
Usaco3.4 "broken Gong rock" band raucous rockers - DP
2022-07-05 20:23:00 【Dimple】
https://www.luogu.com.cn/problem/P2736
The question
Given N ( 1 ≤ N ≤ 20 ) N(1\leq N\leq 20) N(1≤N≤20) song , Choose several songs from them , issue M ( 1 ≤ M ≤ 20 ) M(1\leq M\leq 20) M(1≤M≤20) Zhang CD.
Each sheet CD At most T ( 1 ≤ T ≤ 20 ) T(1\leq T\leq 20) T(1≤T≤20) Minutes of music , One song cannot be divided into two CD in .CD The quantity can be used up , It can also be done .
Choose according to the following criteria :
- Songs must be written in chronological order in all CD Appear on the disk .( notes : The first i i i The creation time of the last song of Zhang pan is earlier than that of i + 1 i+1 i+1 The first song of the disc )
- Select as many songs as possible .
ask , Can be installed M M M Zhang CD The maximum number of songs ?
Ideas
“ Songs must be written in chronological order in all CD Appear on the disk ” This condition shows that you can't be greedy directly .
Consider using dp, The maximum number of songs that can be stored in the current capacity is transferred from the capacity minus the current song size .
and “ One song cannot be divided into two CD in ” This condition indicates that you cannot simply transfer from the previous capacity , We also need to consider whether to pack it in two pieces .
therefore , Define the State f[i, j, k]
Express , For the former i
A song , Before use j
Zhang CD Plus k
minute , The maximum number of songs that can be accommodated .
Then the final state is f[n, m, 0]
.
State shift :
- First, inherit the state of the previous position :
f[i, j, k] = f[i-1, j, k]
; - When additional
k
Minutes is greater than the current song size , You can start fromf[i-1, j, k-a[i]
To transfer :f[i, j, k] = f[i-1, j, k-a[i]] + 1
; - otherwise , It needs to be stored in the previous record , from
f[i-1, j-1, t-a[i]]
To transfer :f[i, j, k] = f[i-1, j-1, t-a[i]] + 1
;
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N][N][N];
signed main(){
int t;
cin >> n >> t >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=t;k++)
{
f[i][j][k] = f[i-1][j][k];
if(k>=a[i]) f[i][j][k] = max(f[i][j][k], f[i-1][j][k-a[i]] + 1);
else if(t-a[i] >= 0 && j >= 1) f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t-a[i]] + 1);
}
}
}
cout << f[n][m][0];
return 0;
}
Experience
State definition should dare to think .
边栏推荐
- 【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
- ROS2专题【01】:win10上安装ROS2
- Fundamentals - configuration file analysis
- 微信小程序正则表达式提取链接
- Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
- 插值查找的简单理解
- 信息学奥赛一本通 1337:【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树
- 基础篇——配置文件解析
- Leetcode (695) - the largest area of an island
- 【数字IC验证快速入门】6、Questasim 快速上手使用(以全加器设计与验证为例)
猜你喜欢
Unity editor extended UI control
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
物联网智能家居基本方法实现之经典
Hong Kong stocks will welcome the "best ten yuan store". Can famous creative products break through through the IPO?
Scala基础【HelloWorld代码解析,变量和标识符】
Leetcode skimming: binary tree 16 (path sum)
走入并行的世界
PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
[quick start of Digital IC Verification] 7. Basic knowledge of digital circuits necessary for verification positions (including common interview questions)
14、Transformer--VIT TNT BETR
随机推荐
【愚公系列】2022年7月 Go教学课程 004-Go代码注释
CTF逆向基础
sun. misc. Base64encoder error reporting solution [easy to understand]
mongodb/文档操作
Leetcode(347)——前 K 个高频元素
c語言oj得pe,ACM入門之OJ~
When JS method passes long type ID value, precision loss will occur
Leetcode skimming: binary tree 12 (all paths of binary tree)
Leetcode (695) - the largest area of an island
Go language | 01 wsl+vscode environment construction pit avoidance Guide
ICTCLAS word Lucene 4.9 binding
2020 CCPC 威海 - A. Golden Spirit(思维),D. ABC Conjecture(大数分解 / 思维)
Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)
Some problems encountered in cocos2d-x project summary
走入并行的世界
DP: tree DP
What is PyC file
Enter the parallel world
nprogress插件 进度条
Is it safe for Galaxy Securities to open an account online?