來源：

時間限制：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[ x_i ][ x_j ]=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;}

總結

以上是生活随笔為你收集整理的【每日一题】6月30日 Growth的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。