当前位置:网站首页>[oiclass] share prizes
[oiclass] share prizes
2022-07-06 14:48:00 【Liujincheng LJC】
Share prizes
Title Description
In the school creative knowledge competition , Mingming and Wenwen got a total of n(1≦ n≦250) A prize , Every prize has a value Vi (1 ≦ Vi ≦ 2,000). They want to share these prizes equally by value , If you can't score equally, try to minimize the gap between them . Now give the number of prizes and their value , Clearly want to calculate the minimum difference after division , And the number of schemes divided .
for example : Yes 5 The value of each prize is :2, 1,8, 4, 16. Mingming and Wenwen are divided into two parts , The first four are part 1+2+4+8=15,16 As a separate part , Then the difference between the two parts :16-15 = 1. This is the division scheme with the smallest gap , And the division method of this scheme is only 1 Kind of .
Prizes of the same value intersect and convert into different schemes , Such as : There are four prizes worth {1, 1, 1, 1}, Yes 6 There are different division schemes , Divide these prizes into two parts , Every part of it 2 A prize .
Input
first line : An integer n(1≦n≦250);
Then there was n That's ok , One integer per row Vi (1 ≦ Vi ≦ 2,000) Represents the value of each prize .
Output
first line : An integer , Represents the minimum difference between the two parts of the division .
The second line : An integer , The number of division schemes representing the minimum difference , The result is right 1,000,000 Seeking remainder (mod 1,000,000).
The sample input #1:
5
2
1
8
4
16
Sample output #1:
1
1
The sample input #2:
4
1
1
1
1
Sample output #2:
0
6
Ideas
First, we can use the idea of dynamic programming :
set up f[i][j] For the former i The value of these prizes is j Different schemes
So the equation of state transition is going to be :
f[i][j] = f[i-1][j]+f[i-1][j-a[i]]
The code written at this time is like this :
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000;
const int N = 300;
int n,a[N],f[N][2000*N];
int maxn = 0;
int main(){
cin >> n;
for(int i=1;i<=n;i++)cin >> a[i],maxn+=a[i];
f[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=maxn;j++){
f[i][j] = (f[i-1][j]+f[i-1][j-a[i]])%MOD;
}
}
int ans=2000*N,cnt=-1;
for(int j=0;j<=maxn;j++){
if(abs((maxn-j)-j)<ans){
ans = abs((maxn-j)-j);
cnt = f[n][j];
}
}
cout << ans << endl << cnt << endl;
return 0;
}
result : MLE
The space complexity of this code is too high . So I put f The first dimension of is changed to a scrolling array :
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000;
const int N = 260;
int n,a[N],f[3][2000*N];
bool vis[3][2000*N];
int maxn = 0;
int main(){
cin >> n;
for(int i=1;i<=n;i++)cin >> a[i],maxn+=a[i];
f[0][0] = 1;
vis[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=maxn;j++){
if(j-a[i]>=0){
f[i%2][j] = (f[(i-1)%2][j]+f[(i-1)%2][j-a[i]])%MOD;
vis[i%2][j]= vis[(i-1)%2][j] || vis[(i-1)%2][j-a[i]];
}
else{
f[i%2][j] = f[(i-1)%2][j];
vis[i%2][j] = vis[(i-1)%2][j];
}
}
}
int ans=2000*N,cnt=-1;
for(int j=0;j<=maxn;j++){
if(abs((maxn-j)-j)<ans and vis[n%2][j]!=0){
ans = abs((maxn-j)-j);
cnt = f[n%2][j];
}
}
cout << ans << endl << cnt << endl;
return 0;
}
This time it became TLE
Time optimization , take mod The final answer is :
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000;
const int N = 260;
int n,a[N],sum[N],f[3][2000*N];
bool vis[3][2000*N];
int maxn = 0;
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
maxn+=a[i];
sum[i]=sum[i-1]+a[i];
}
f[0][0] = 1;
vis[0][0] = 1;
for(int i=1;i<=n;i++){
int I2=i%2,I12=(i-1)%2;
for(int j=0;j<=sum[i];j++){
if(j-a[i]>=0){
f[I2][j] = f[I12][j]+f[I12][j-a[i]];
if(f[I2][j]>=MOD) f[I2][j]-=MOD;
vis[I2][j]= vis[I12][j] || vis[I12][j-a[i]];
}
else{
f[I2][j] = f[I12][j];
vis[I2][j] = vis[I12][j];
}
}
}
int ans=2000*N,cnt=-1;
for(int j=0;j<=maxn;j++){
if(abs((maxn-j)-j)<ans and vis[n%2][j]!=0){
ans = abs((maxn-j)-j);
cnt = f[n%2][j];
}
}
cout << ans << endl << cnt << endl;
return 0;
}
Turned into AC !
边栏推荐
- “Hello IC World”
- Statistics, 8th Edition, Jia Junping, Chapter 11 summary of knowledge points of univariate linear regression and answers to exercises after class
- 《统计学》第八版贾俊平第二章课后习题及答案总结
- 【指针】求二维数组中最大元素的值
- 《统计学》第八版贾俊平第四章总结及课后习题答案
- 我的第一篇博客
- Function: find the root of the equation by Newton iterative method
- To brush the video, it's better to see if you have mastered these interview questions. Slowly accumulating a monthly income of more than 10000 is not a dream.
- Wang Shuang's detailed learning notes of assembly language II: registers
- [pointer] find the largest string
猜你喜欢
New version of postman flows [introductory teaching chapter 01 send request]
Transplant hummingbird e203 core to Da Vinci pro35t [Jichuang xinlai risc-v Cup] (I)
Get started with Matplotlib drawing
“Hello IC World”
《統計學》第八版賈俊平第七章知識點總結及課後習題答案
Apache APIs IX has the risk of rewriting the x-real-ip header (cve-2022-24112)
servlet中 servlet context与 session与 request三个对象的常用方法和存放数据的作用域。
Es full text index
数字电路基础(四) 数据分配器、数据选择器和数值比较器
High concurrency programming series: 6 steps of JVM performance tuning and detailed explanation of key tuning parameters
随机推荐
《统计学》第八版贾俊平第九章分类数据分析知识点总结及课后习题答案
Realize applet payment function with applet cloud development (including source code)
. Net6: develop modern 3D industrial software based on WPF (2)
Statistics 8th Edition Jia Junping Chapter XIII Summary of knowledge points of time series analysis and prediction and answers to exercises after class
Four methods of exchanging the values of a and B
Captcha killer verification code identification plug-in
Wang Shuang's detailed learning notes of assembly language II: registers
Uibutton status exploration and customization
Statistics 8th Edition Jia Junping Chapter 1 after class exercises and answers summary
指针 --按字符串相反次序输出其中的所有字符
《统计学》第八版贾俊平第七章知识点总结及课后习题答案
王爽汇编语言学习详细笔记一:基础知识
How to earn the first pot of gold in CSDN (we are all creators)
Proceedingjoinpoint API use
Statistics, 8th Edition, Jia Junping, Chapter 11 summary of knowledge points of univariate linear regression and answers to exercises after class
[pointer] use the insertion sorting method to arrange n numbers from small to large
Functions: Finding Roots of equations
内网渗透之内网信息收集(三)
《统计学》第八版贾俊平第四章总结及课后习题答案
Sword finger offer 23 - print binary tree from top to bottom