大连精美网站制作,网站建设云,wordpress如何关闭自动更新,免费空间忘记密码解决方法来源#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 1048576K#xff0c;其他语言2097152K
64bit IO Format: %lld文章目录题目描述题解#xff1a;代码#xff1a;题目描述 弱弱有两个属性a和b#xff0c;这两个属性初始的时…来源
时间限制C/C 1秒其他语言2秒
空间限制C/C 1048576K其他语言2097152K
64bit IO Format: %lld文章目录题目描述题解代码题目描述 弱弱有两个属性a和b这两个属性初始的时候均为0每一天他可以通过努力让a涨1点或b涨1点。 为了激励弱弱努力学习我们共有n种奖励第i种奖励有xiyizi三种属性若a≥ xi且b≥ yi则弱弱在接下来的每一天都可以得到zi的分数。 问m天以后弱弱最多能得到多少分数。 输入描述: 第一行一个两个整数n和m1≤ n≤ 10001≤ m≤ 2000000000。 接下来n行每行三个整数xiyizi1≤ xi,yi≤ 10000000001≤ zi ≤ 1000000。 输出描述: 一行一个整数表示答案。 示例1 输入 复制
2 4
2 1 10
1 2 20输出 复制
50备注: 在样例中弱弱可以这样规划第一天a涨1第二天b涨1第三天b涨1第四天a涨1。 共获得00203050分。 题解
dp [ i ] [ j ]表示在sum ij天两种属性分别是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] ansmax(ans,dp[i][j](m-i-j)*a[i][j]) 如果我们在这一天可以获得a[][]的分数那之后的每一天都可以获得在此之后还有m-i-j天所以直接加上这个分数在以后天数获得的总和 本题的xiyim都比较大记得要先离散化。
代码
#includebits/stdc.h
using namespace std;
const int maxn1400;
int dp[maxn][maxn];
int a[maxn][maxn];
int x[maxn],y[maxn],z[maxn];
int b[maxn],c[maxn];
int main()
{int sum0;int n,m;cinnm;for(int i1;in;i){cinx[i]y[i]z[i];b[i]x[i];c[i]y[i];}sort(b1,b1n);sort(c1,c1n);int ant1unique(b1,b1n)-b-1;int ant2unique(c1,c1n)-c-1;for(int i1;in;i){x[i] lower_bound(b1,b1ant1,x[i])-b;y[i] lower_bound(c1,c1ant2,y[i])-c;a[x[i]][y[i]] z[i];}for(int i1;iant1;i)for(int j1;jant2;j){a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1];}for(int i1;iant1;i)for(int j1;jant2;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 i1;iant1;i)for(int j1;jant2;j){if(b[i]c[i]m)break;summax(sum,dp[i][j](m-b[i]-c[i])*a[i][j]);coutsumendl;}coutsum;return 0;}
