Problem E : Easy Project
Description
Mia and her friends are preparing for the project that the professor has given them!
They received a huge project, indeed, and this entire project can be divided into n tasks, numbered 1, 2, ..., n. It takes anyone (who is assigned the task) w units of time to finish the i-th task (1 ≤ i ≤ n).
There are m dependencies between these tasks, i.e. some tasks must be finished before anyone can start a certain task.
It is time to assign the tasks. They want the entire project to be finished as soon as possible. Mia, however, finds that some tasks do not have to start as early as possible, and even some slight delay of these tasks will not cause the delay of the entire project.
Now, Mia wants you to show her how long each task can be delayed at most without affecting the entire project. See Explanations for the Sample Input and Output for details.
To simplify the problem, the dependencies have the following constraints:
- You start from task 1. Task 1 is always the first task. And, task 1 is the only task that you do not have to finish any other task before you can start.
- The last task is always task n. And, task n is the only task that you do not have to finish before you can start any other task, which means once you have finished task n, the entire project is finished.
- There will be no conflicts in the given dependencies. The entire project can always be finished. This can be easily seen from the input.
Explanations for the Sample Input and Output
As is shown below, since we want the entire project to be finished as soon as possible, task 1 and task 9 cannot be delayed.
If we ignore some of the dependencies, task 3, task 6 and task 8 take 29 units of time to finish in total. Compared to task 2, task 4 and task 7 which take 26 units of time, and task 3, task 5 and task 7 which take 22 units of time, task 3, task 6 and task 8 take the longest time to finish, which suggests, in this case, none of them can be delayed or the entire project will definitely be affected.
According to the above calculation, task 3, task 5 and task 7 take 7 units of time less than task 3, task 6 and task 8 take, while task 2, task 4 and task 7 take only 3 units of time less than task 3, task 6 and task 8 take. So, task 2, task 4 and task 7 can be delayed 3 units of time at most, and task 5 can be delayed 7 units of time at most.
Notice that the answer is only the maximum units of time that each task can be delayed, i.e. we consider the delay for each task, separately. For example, we now know that task 4 can be delayed 3 units of time at most. If task 4 is really delayed 3 units of time, task 2 and task 7 cannot be delayed, or the entire project will be affected!
Input
There are multiple test cases (no more than 120).
For each test case, the first line contains two positive integers n and m. n is the number of tasks, and m is the number of dependencies. (1 ≤ n ≤ 100,000, 1 ≤ m ≤ 1,000,000)
The second line contains n positive integers w, w, ..., w, the i-th of which is the required units of time to finish the i-th task. (1 ≤ w ≤ 1,000, 1 ≤ i ≤ n)
There are m lines following, the i-th of which contains two positive integers u and v, which means you need to finish task u before you can start task v (1 ≤ u < v ≤ n, 1 ≤ i ≤ m).
It is guaranteed that the sum of n over all test cases is less than 1,000,000, and the sum of m over all test cases is less than 10,000,000.
Output
For each test case, output a single line containing n integers (separated by a space), the i-th of which is how long the i-th task can be delayed at most. Notice that the end of line does not have any extra spaces.
Sample Input
9 10 4 9 4 6 7 12 11 13 3 1 2 1 3 2 4 3 5 3 6 4 7 5 7 6 8 7 9 8 9
Sample Output
0 3 0 3 7 0 3 0 0
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=1e6+5; 5 int n,m,tot; 6 7 int lists[maxn][3]; 8 int connect[maxn][2]; 9 10 struct line{int x,y;}; 11 bool cmp(const line a,const line b) 12 { 13 return a.y<b.y; 14 } 15 line s[maxn]; 16 17 int main() 18 { 19 while(cin>>n>>m) 20 { 21 memset(lists,0,sizeof(lists)); 22 for(int i=1; i<=n; ++i) 23 { 24 cin>>lists[i][0]; 25 26 } 27 lists[1][1]=lists[1][2]=0; 28 int a,b; 29 for(int i=0; i<m; ++i) 30 { 31 cin>>a>>b; 32 s[i].x=a; 33 s[i].y=b; 34 lists[b][1]=max(lists[b][1],lists[a][0]+lists[a][1]); 35 } 36 for(int i=2; i<=n; ++i) 37 { 38 lists[i][2]=0x3f3f3f; 39 } 40 lists[n][2]=lists[n][1]; 41 lists[1][2]=0; 42 sort(s,s+m,cmp); 43 for(int i=m-1; i>=0; --i) 44 { 45 lists[s[i].x][2]=min(lists[s[i].x][2],lists[s[i].y][2]-lists[s[i].x][0]); 46 } 47 for(int i=1; i<=n; ++i) 48 { 49 if(i==1) 50 cout<<lists[i][2]-lists[i][1]; 51 else 52 cout<<" "<<lists[i][2]-lists[i][1]; 53 } 54 cout<<endl; 55 } 56 57 return 0; 58 }
Problem G : Gaming with Mia
Description
Mia is learning data structures, this semester. After her boyfriend, John, has given so many problems to her, this time, Mia gives John an interesting problem, or rather, an intellectual game.
In this problem, you are given an integer sequence a, a, ..., a (-1 ≤ a ≤ 1, 1 ≤ i ≤ n). You are going to determine n - 1 operators op, op, ..., op (op is either '+' or '*', 1 ≤ i ≤ n - 1) so that the result of the expression S = a op a op a op ... op a op a is maximized.
Mia is only interested in the maximum result S, but John is unable to tell. Now, John has turned to you for help!
Explanations for the Sample Input and Output
For the first test case, there is only one integer, so we just need to output it: S = 1.
For the second test case, S = 1 + 1 + 1 + 0 = 3.
For the third test case, S = (-1) * (-1) + 0 = 1.
Input
There are multiple test cases (no more than 120).
For each test case, the first line contains one integer n (1 ≤ n ≤ 100,000).
The second line contains n integers a, a, ..., a (-1 ≤ a ≤ 1, 1 ≤ i ≤ n).
There are no more than 10 test cases with n > 1,000.
Output
For each test case, output one integer which is the maximum result S.
Sample Input
1 1 4 1 1 1 0 3 -1 -1 0
Sample Output
1 3 1
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=1e6+5; 5 int n,m,tot; 6 7 int num[maxn]; 8 int dp[maxn]; 9 10 int multiply(int x,int y) 11 { 12 int ans=1; 13 for(int i=x;i<=y;++i) 14 { 15 ans*=num[i]; 16 } 17 return ans; 18 } 19 20 int main() 21 { 22 while(cin>>n) 23 { 24 memset(dp,0,maxn); 25 memset(num,0,maxn); 26 for(int i=1;i<=n;++i) 27 { 28 cin>>num[i]; 29 } 30 dp[1]=num[1]; 31 dp[2]=max(num[1]+num[2],num[1]*num[2]); 32 for(int i=3;i<=n;++i) 33 { 34 int k=min(10,i); 35 for(int j=1;j<=k;++j) 36 { 37 dp[i]=max(dp[i],dp[i-j]+multiply(i-j+1,i)); 38 } 39 } 40 cout<<dp[n]<<endl; 41 } 42 return 0; 43 }
还有一题过不了，过了再补上来ba~