Some Dynamic Programming Problems#
Also from YiZhong OJ
[USACO3.1.2] Total Score#
Description#
The more points a student scores in our USACO competition, the happier we are. We try to design our competition so that people can score as many points as possible, and we need your help.
We can choose competition problems from several categories. Here, a "category" refers to a collection of competition problems, solving the problems in the collection requires the same amount of time and can earn the same number of points. Your task is to write a program to tell the USACO staff how many problems should be selected from each category so that the total time spent on solving the problems is within the competition time limit and the total score is maximized.
The input includes the competition time: M, the number of problem categories: N, and. Each subsequent line will include two integers to describe a "category": the first integer indicates the score that can be obtained by solving this type of problem (1 <= points <= 10000), and the second integer indicates the time required to solve this type of problem (1 <= minutes <= 10000). Your program should determine how many problems should be selected from each "category" so that the maximum score can be obtained within the competition time limit.
The number of problems from any "category" can be any non-negative number (0 or more).
Input#
The first line: M, N - the competition time and the number of problem "categories". The 2nd to N+1 lines: two integers: the score and time for each "category" problem.
Output#
A single line including the maximum score that can be obtained within the given constraints.
Input Example 1#
300 4
100 60
250 120
120 100
35 20
Output Example 1#
605
Hint#
1 <= M <= 10,000 1 <= N <= 10,000 The score of each problem is within the range of 1..10000; the time required to solve the problem is within the range of 1..10000.
Idea#
Complete backpack problem, fill in order
i: consider the first i problems
j: total time
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=10000+5;
struct js{
int tm,mark;
};
int n,m;
js a[MAXN];
int f[MAXN];
int main(){
cin>>m>>n;
for(int i=1;i<=n;++i){
cin>>a[i].mark>>a[i].tm;
}
f[0]=0;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(i-a[j].tm>=0){
if(f[i-a[j].tm]+a[j].mark>f[i]){
f[i]=f[i-a[j].tm]+a[j].mark;
}
}
}
}
cout<<f[m]<<endl;
return 0;
}
[Training Problem] Speak Your Mind#
Description#
You have been patient for too long. Now is the time to speak your mind to everyone.
Assume you express your opinion to n people. After speaking to the i-th person, your health index will decrease by g[i], and your happiness index will increase by h[i]. You can speak to each person at most once, and you don't have to follow a specific order.
Your goal is to maximize your happiness. Assuming your initial health index is 1000 and your happiness index is 0. If your health index is 0 or negative, even if you gain more happiness, you will only die in pain.
Now write a program to calculate the maximum happiness index you can get.
Input#
The first line: 1 positive integer N, indicating the number of people. The second line: N integers, the i-th integer indicates the health index you will lose when speaking to the i-th person g[i]. The third line: N integers, the i-th integer indicates the happiness index you will gain when speaking to the i-th person h[i].
Output#
1 line in total, 1 integer, indicating the maximum happiness index you can get.
Input Example 1#
3
10 210 790
200 300 250
Output Example 1#
500
Hint#
For 30% of the data: 1<=N<=20 For 100% of the data: 1<=N<=200 All data: 0
Idea#
0/1 backpack, fill in reverse order
i: the i-th person
j: the health index deducted
#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) (a>b)?(a):(b)
#define fuck(a,b,c) for(int a=b;a<=c;++a)
#define shit(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
const int MAXN=200+5;
int f[1005];
int g[MAXN],h[MAXN];
int n;
int main(){
cin>>n;
memset(f,0,sizeof(f));
fuck(i,1,n){
cin>>g[i];
}
fuck(i,1,n){
cin>>h[i];
}
fuck(i,1,n){
shit(j,1000,1){
if(j-g[i]>0){
f[j]=max(f[j],f[j-g[i]]+h[i]);
}
}
}
cout<<f[1000]<<endl;
return 0;
}
PS#
This setting is really strange...
Because you express your opinion to someone and then get hit
Then you will lose health... ...
(The code is slightly mischievous
[Training Problem] Maximum Divisor Sum#
Description#
Select several different positive integers whose sum does not exceed S, so that the sum of their divisors (excluding themselves) is maximized!
Input#
An integer S.
Output#
Output the maximum sum of divisors.
Input Example 1#
11
Output Example 1#
9
Hint#
For 30% of the data: S<=10 For 100% of the data: S<=1000
Idea#
Thanks to
Perisino(for providing the second idea)
s[i]represents the sum of divisors ofi
My idea#
Originally I thought like this:
f[which number][sum]=sum of divisors;
f[i][j]=max(f[i-1][j-i]+s[i],f[i-1][j]);
Then I found out that it was wrong
Then I modified Perisino's method
Then I found out that the function for calculating the sum of divisors was wrong.
Here, the sum of divisors does not include itself, but I initially added itself
Then I found out that it was correct
Great~
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=1005;
deque<int> ys[MAXN];
deque<int> s;
int f[MAXN];
int yueshuhe(int x);
int main(){
int he;
cin>>he;
yueshuhe(he);
for(int i=1;i<=he;++i){
for(int j=i;j<=he;++j){
f[j]=max(f[j-i]+s[i],f[j]);
}
}
cout<<f[he]<<endl;
return 0;
}
int yueshuhe(int x){
s.resize(x+5);
for(int i=1;i<=x;++i){
for(int j=1;j<=x/i;++j){
ys[i*j].push_back(i);
s[i*j]+=i;
}
s[i]-=i;
}
}
Perisino's idea#
f[i]=max(f[i],s[j]+f[i-j]);
Outer loop: sum is i
Inner loop: j plus the selected number = i
So
for(int i=1;i<=he;++i){
for(int j=1;j<=i;++j){
f[i]=max(f[i],f[i-j]+s[j]);
}
}
PS:
I always thought that k was used to fill k backpacks. Actually, this is the reason why I was afraid I couldn't do it.
For this reason, I also found such a solution...
Shameful!