[ACM] n划分数m部分,它要求每一个部分,并采取了最大的产品(间隔DP)
产品 一个 最大 部分 DP 要求 划分 ACM
2023-09-14 09:08:08 时间
A - 爱管闲事
春希很爱管闲事,他每天都会抽出时间帮助一些同学,因为春希很死板,出于公平性。春希不会先帮助后来找他的同学。
如今有
依据事情的重要性,春希帮助不同同学会有不同的快乐值,而春希获得的总的快乐值为每天获得的快乐值的乘积。
如今给出
Input
第一行为一个整数
每组数据,第一行两个整数
表示须要帮助的同学的数量,和天数。
第二行为
Output
每组数据输出一行。一个整数,表示最大的快乐值。
Sample input and output
Sample Input | Sample Output |
---|---|
1 5 3 3 2 1 4 5 |
125 |
dp[j][i]表示前j个数分为i部分的和的乘积的最大值。測试用例中(3+2)*(1+4)*5=125
三重循环。
dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k]));
关键代码:
for(int i=1;i<=m;i++) for(int j=n;j>=i;j--) for(int k=i-1;k<j;k++) { dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k])); }
代码:
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int maxn=25; int dp[maxn][maxn]; int num[maxn],sum[maxn]; int t,n,m; int main() { cin>>t; while(t--) { cin>>n>>m; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=1; sum[0]=0; for(int i=1;i<=n;i++) { cin>>num[i]; sum[i]=sum[i-1]+num[i]; } for(int i=1;i<=m;i++) for(int j=n;j>=i;j--) for(int k=i-1;k<j;k++) { dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k])); } cout<<dp[n][m]<<endl; } return 0; }一開始写的一维的,但是一直WA,不知道为什么。求解。
错误的一维代码:
#include <iostream> #include <string.h> #include <algorithm> using namespace std; int sum[25]; int num[25]; int dp[25]; int t; int n,m; int main() { cin>>t; while(t--) { sum[0]=0; dp[0]=1; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>num[i]; sum[i]=sum[i-1]+num[i]; dp[i]=1; } for(int i=1;i<=m;i++) { for(int j=n;j>=i;j--) { for(int k=i-1;k<j;k++) { dp[j]=max(dp[j],dp[k]*(sum[j]-sum[k])); } } } cout<<dp[n]<<endl; } return 0; }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
相关文章
- 在Spring Cloud中集成和使用CSE快速实现商业产品
- 【权限设计】一个案例,三个角色,简单说下B端产品的权限设计
- 一个字稳,云原生产品家族支撑冬奥会九大业务场景,打造云上奥运新体验
- 产品运营数据分析—SPSS数据分组案例
- Product - 产品经理 - 转型
- 开发一个电商产品
- 一个十年SAP CRM老司机对产品主数据的理解
- 如何调试SAP CRM产品主数据应用后台ABAP端抛出的错误消息
- 一种基于事件驱动架构的 SAP 产品集成方案介绍
- 响应式编程在 SAP 标准产品 UI 开发中的一个实践
- Algorithm:论一个产品经理的十八般武艺
- 云上人第七代产品简单的代码
- 码农的产品思维培养第2节----一个需求的奋斗史(人人都是产品经理)
- 研发思维05----嵌入式智能产品外观设计之经典