poj 1821 dp+単調なキュー

Fence
Time Limit: 1000 MS
 
メモリLimit: 30000 K
Total Submissions: 3858
 
Acceepted: 1176
Description
A team of k(1==K==100)works shound paint a fence which contains N(1==N==16,000)plnks numbed from 1 to N from to right.Each worker i(1==i==K)shuld sit front of the plantmant andThis interval shound contain the Si plank.Also a work shound not paint more than Li plank and for each painted plank he shound receive Pi.(1==Pi==10,000).A plnk shoud painted by morrem.morn. 
Being the team's leader you want to determine for each work the interval that he shound paint,knowing that the total income shoult be maximal.The total income represents the sum of the workers personicome. 
Write a program that determines the total maximal income Outined by the K work. 
Input
The input contains: 
Input 
N K 
L 1 P 1 S 1 
L 2 P 2 S 2 
… 
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 plnk 
Si-the plank in front of which sits the workker i 
Output
The output contains a single integer、the total maximal income.
Sample Input

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

Sample Output

17

ベント

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define maxn 16001
#define maxk 101
typedef long long ll;

int n, k;
ll dp[maxn];
struct Data
{
    ll l, p, s;
    bool operator  que;
            for(int j = max(a[i].s-a[i].l, (ll)0); j < a[i].s; j++){
                while(!que.empty()){
                    int last = que.back();
                    if(dp[last]+a[i].p*(i-last) <= dp[j]+a[i].p*(i-j))
                        que.pop_back();
                    else break;
                }
                que.push_back(j);
            }

            for(int j = a[i].s; j < a[i].s+a[i].l && j <= n; j++){
                while(!que.empty() && que.front() < j-a[i].l) que.pop_front();

                if(!que.empty())
                dp[j] = max(dp[j], dp[que.front()]+a[i].p*(j-que.front()));
            }
        }

        ll ans = 0;
        for(int i = 0; i <= n; i++)
            ans = max(ans, dp[i]);
        printf("%I64d
", ans);
    }
    return 0;
}