【每日一题】6月30日 Growth

来源：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld

@[toc]

题目描述

弱弱有两个属性a和b，这两个属性初始的时候均为0，每一天他可以通过努力，让a涨1点或b涨1点。
为了激励弱弱努力学习，我们共有n种奖励，第i种奖励有xi，yi，zi三种属性，若a≥ xi且b≥
yi，则弱弱在接下来的每一天都可以得到zi的分数。 问m天以后弱弱最多能得到多少分数。 输入描述: 第一行一个两个整数n和m（1≤ n≤
1000，1≤ m≤ 2000000000）。 接下来n行，每行三个整数xi，yi，zi（1≤ xi,yi≤ 1000000000，1≤
zi ≤ 1000000）。

输出描述:
一行一个整数表示答案。
示例1
输入
复制

2 4
2 1 10
1 2 20

输出
复制

50

备注:

在样例中，弱弱可以这样规划：第一天a涨1，第二天b涨1，第三天b涨1，第四天a涨1。 共获得0+0+20+30=50分。

题解：

dp [ i ] [ j ]表示在sum = i+j天，两种属性分别是i和j所得到的分数（一共）
根据题意可得：
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]
a[i][j]表示属性分别是i和j可获得大分数（当天）
那a[i][j]是怎么得到的？
我们用二维前缀和的思想来实现：
a[ xi ][ xj ]=z
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
整合一下最后答案就是：
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]
ans=max(ans,dp[i][j]+(m-i-j)*a[i][j])
如果我们在这一天可以获得a[][]的分数，那之后的每一天都可以获得，在此之后还有（m-i-j）天，所以直接加上这个分数在以后天数获得的总和
本题的xi，yi，m都比较大记得要先离散化。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1400;
int dp[maxn][maxn];
int a[maxn][maxn];
int x[maxn],y[maxn],z[maxn];
int b[maxn],c[maxn];
int main()
{
    int sum=0;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>z[i];
        b[i]=x[i];
        c[i]=y[i];
    }
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    int ant1=unique(b+1,b+1+n)-b-1;
    int ant2=unique(c+1,c+1+n)-c-1;
    for(int i=1;i<=n;i++)
    {
        x[i] = lower_bound(b+1,b+1+ant1,x[i])-b;
        y[i] = lower_bound(c+1,c+1+ant2,y[i])-c;
        a[x[i]][y[i]] += z[i];
    }
    for(int i=1;i<=ant1;i++)
    for(int j=1;j<=ant2;j++)
    {
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    }
    for(int i=1;i<=ant1;i++)
    for(int j=1;j<=ant2;j++)
        {
            dp[i][j] = max(dp[i-1][j]+(b[i]-b[i-1]-1)*a[i-1][j],dp[i][j-1]+(c[j]-c[j-1]-1)*a[i][j-1]) + a[i][j];
        }
    for(int i=1;i<=ant1;i++)
    for(int j=1;j<=ant2;j++)
    {
        if(b[i]+c[i]>m)break;
        sum=max(sum,dp[i][j]+(m-b[i]-c[i])*a[i][j]);
        cout<<sum<<endl;
    }
    cout<<sum;
    return 0;

}