[oiclass] share prizes

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 ！