POJ 1821 Fence
Fence
This problem will be judged on PKU. Original ID: 1821
64-bit integer IO format: %lld Java class name: Main
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = ;
struct Worker{
int L,S,P;
bool operator<(const Worker &rhs) const{
return S < rhs.S;
}
}a[maxn];
int n,m,L[maxn],R[maxn],dp[][maxn],q[maxn]; int main(){
while(~scanf("%d%d",&n,&m)){
for(int i = ; i <= m; ++i)
scanf("%d%d%d",&a[i].L,&a[i].P,&a[i].S);
sort(a + , a + m + );
for(int i = ; i <= m; ++i){
L[i] = max(,a[i].S - a[i].L);
R[i] = min(n,a[i].S + a[i].L - );
}
for(int i = ; i <= m; ++i){
for(int j = ; j <= R[i]; ++j)
dp[i][j] = dp[i-][j];
int hd = ,tl = ;
for(int j = L[i]; j < a[i].S; ++j){
while(hd < tl && dp[i-][j] - j*a[i].P >= dp[i-][q[tl-]] - q[tl-]*a[i].P) --tl;
q[tl++] = j;
}
for(int j = a[i].S; j <= R[i]; ++j){
while(hd < tl && j - q[hd] > a[i].L) ++hd;
dp[i][j] = max(dp[i-][j],dp[i][j-]);
dp[i][j] = max(dp[i][j],dp[i-][q[hd]] + (j - q[hd])*a[i].P);
}
for(int j = R[i] + ; j <= n; ++j)
dp[i][j] = max(dp[i-][j],dp[i][j-]);
}
int ret = ;
for(int i = ; i <= n; ++i)
ret = max(ret,dp[m][i]);
printf("%d\n",ret);
}
return ;
}
最新文章
- 好程序员带你了解一下HTTPS和SSL/TLS协议的背景与基础
- leetcode-【hard】273. Integer to English Words
- TreeMap源码分析
- 【BZOJ-1912】patrol巡逻 树的直径 + DFS(树形DP)
- 如何正确使用css中vertical-align
- acl拒绝访问流量
- JS 时分秒验证
- Top命令内存占用剖析
- Visual C++ 打印编程技术-打印基础知识
- Qt 内存泄漏测试
- spring自带定时器
- spring的配置和使用
- Windows Java安装
- 基于kettle的简单HTTP接口监控
- CentOS6下4网口绑定双IP
- python自学第9天,装饰器
- 在Java中调用C/C++本地库
- ubuntu系统升级和其他相关操作记录
- 结合 Redis 实现同步锁
- 隐藏和显示服务器端控件以及Html控件