Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 6122 | Accepted: 1972 |
Description
Being the team's leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.
Write a program that determines the total maximal income obtained by the K workers.
Input
Input
N K
L1 P1 S1
L2 P2 S2
...
LK PK SK
Semnification
N -the number of the planks; K ? the number of the workers
Li -the maximal number of planks that can be painted by worker i
Pi -the sum received by worker i for a painted plank
Si -the plank in front of which sits the worker i
Output
Sample Input
8 4
3 2 2
3 2 3
3 3 5
1 1 7
Sample Output
17
Hint
the worker 1 paints the interval [1, 2];
the worker 2 paints the interval [3, 4];
the worker 3 paints the interval [5, 7];
the worker 4 does not paint any plank
Source
当我们循环j,k时,可以把i看成是定值,于是对于这条方程我们可以进行一定的变形,将j和k分离。
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f int k, n;
struct node{
int l, s, p;
}worker[];
int que[], dp[][];
bool cmp(node a, node b)
{
return a.s < b.s;
} int cal(int i, int k)
{
return dp[i - ][k] - worker[i].p * k;
} int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d%d", &n, &k)!= EOF){
for(int i = ; i <= k; i++){
scanf("%d%d%d", &worker[i].l, &worker[i].p, &worker[i].s);
//printf("%d%d%d\n", worker[i].l, worker[i].s, worker[i].p);
}
sort(worker + , worker + + k, cmp); /*for(int i = 1; i <= k; i++){
printf("%d%d%d\n", worker[i].l, worker[i].s, worker[i].p);
}*/
for(int i = ; i <= k; i++){
int l = , r = ;
for(int x = max(, worker[i].s - worker[i].l); x <= worker[i].s - ; x++){
while(l <= r && cal(i, que[r]) <= cal(i, x)){
r--;
}
que[++r] = x;
}
for(int j = ; j <= n; j++){
dp[i][j] = max(dp[i - ][j], dp[i][j - ]);
if(j >= worker[i].s){
while(l <= r && que[l] < j - worker[i].l)l++;
if(l <= r){
dp[i][j] = max(dp[i][j], cal(i, que[l]) + worker[i].p * j);
}
//cout<<dp[i][j]<<endl;
}
}
} //int ans = 0;
//for(int i = 1; i <= n; i++){
// ans = max(ans, dp[k][i]);
//}
printf("%d\n", dp[k][n]);
}
}