来源：
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
弱弱有两个属性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;
}
京公网安备 11010502036488号