NKPANO – spoj

Đề bài:

Thuật toán:

  • Sắp xếp các công nhân tăng dần theo S
  • Gọi F[i] là tổng tiền công lớn nhất nếu sơn đến vạch i.
    Với mỗi công nhân thứ k: F[i]=max(F[i],F[j-1]+(i-j+1)*P[k]), trong đó: S[k]<=i<=S[k]+L[k]-1, i-L[k]+1<=j<=S[k]

Code:

#include <bits/stdc++.h>
#define maxn 16010
using namespace std;
int n,k,l;
int f[maxn+1],maxf[maxn+1],maxr[maxn+1];
struct  te{
    int l,p,s;
};
te a[102];
template <typename T> inline void read(T &x){
	x = 0; char c;
	while (!isdigit(c = getchar())) {}
	do x = x * 10 + c - '0'; while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x){
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
void    docdl(){
    read(n); read(k);
    for(int i=1;i<=k;i++){
        read(a[i].l);
        read(a[i].p);
        read(a[i].s);
    }
}
bool    cmp(te a,te b){
    return (a.s<=b.s);
}
void    xuli(){
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        maxr[a[i].s+1]=-1000000000;
        for(int j=a[i].s;j>=max(a[i].s-a[i].l+1,1);j--) maxr[j]=max(maxr[j+1],maxf[j-1]-(int)j*a[i].p);
        for(int j=a[i].s;j<=min(a[i].s+a[i].l-1,n);j++){
            f[j]=max(f[j],maxr[max(j-a[i].l+1,1)]+(int)(j+1)*a[i].p);
            maxf[j]=max(f[j],maxf[j-1]);
        }
        for(int j=1;j<=n;j++) maxf[j]=max(maxf[j],maxf[j-1]);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    write(res);
}
int     main(){
    docdl();
    xuli();
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*