題干：

鏈接：https://ac.nowcoder.com/acm/contest/886/J?&headNav=acm&headNav=acm&headNav=acm&headNav=acm
來源：牛客網
?

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.

In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j - 1)-th level, the player can pay cijc_{i j}cij? pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.

Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of djd_{j}dj? pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.

Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

輸入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, m (1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000), representing the number of technologies and the number of levels respectively.The i-th of the next n lines contains m integers, where the j-th number is cijc_{i j}cij? (?109≤cij≤109-10^{9} \leq c_{i j} \leq 10^{9}?109≤cij?≤109).The last line contains m integers, where the j-th number is djd_{j}dj? (?109≤dj≤109-10^{9} \leq d_{j} \leq 10^{9}?109≤dj?≤109).We ensure that the sum of?n?mn \cdot mn?m in all test cases is at most 2×1062 \times 10^{6}2×106.

輸出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer(in pokedollars) to this test case.

示例1

輸入

復制

2 2 2 1 2 2 -1 4 1 3 3 1 2 3 1 2 3 1 2 3 6 7 8

輸出

復制

Case #1: 2 Case #2: 4

說明

?

In the first example, Rowlet can upgrade the first technology to level 1 and the second technology to level 2, which costs 1 + 2 - 1 = 2 pokedollars, but Rowlet can get 4 pokedollars as the bonus of upgrading all technologies to level 1, so the answer is 4 - 2 = 2 pokedollars.?

?

In the second example, Rowlet can upgrade all technologies to level 2, which costs 1×3+2×3=91\times3 + 2\times3=91×3+2×3=9 pokedollars, but Rowlet can get 6 pokedollars as the bonus of upgrading all technologies to level 1 and 7 pokedollars as the bonus of upgrading all technologies to level 2, so the answer is 6 + 7 - 9 = 4 pokedollars.

題目大意：

就是給你n個技能，每個技能最高升到m級，只能從下往上連續的點技能(n*m矩陣)每升一級就是耗費Cij錢，這個Cij可能是負的，如果所有技能都升到或者說超過j等級，就會獲得Dj錢，這個Dj也有可能是負值，讓你求你最多得到多少錢（技能沒有固定說要升到多少級，你也可以不升，這樣就獲得了0）

解題報告：

直接枚舉最小等級的做法我們就不介紹了哈，比較簡單，，而且其實不用線段樹求后綴最小值的。直接可以預處理出來后綴最小值，然后直接取就可以，時間復雜度是O(n*m)的。

這里說另外一種dp方式：

dp[i][j]代表前i個技能升級到最小等級是j 的最大收益。根據這個最小等級j是否來自第i個技能，顯然有轉移方程：

dp[i][j]=max(①，②)

①dp[i-1][j]+第i行的max[j,m]? ? ? ? ? ? ? ②前i-1行的max[j,m] + 第i行的sum[j]。

當然如果這樣做的話，需要再用dp預處理一個東西dd[][]數組，dd[i][j]代表前i個物品只能取后j種等級，且每種科技中只能取一個值的最小收益（但因為給定的值的含義是花費，所以可以認為是給定數據的最大值）。

然后幾個細節注意一下就好了。比如ans不能在dp的過程中取（這是個廢話，，麻瓜錯誤）。再比如 i==1 的時候要跳過②那種情況。其實活著直接i==1的時候特殊處理一下就行。再比如suf[][m+1]必須要初始化，就跟前綴和數組一樣只不過平時sum[0]=0了所以沒管。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e3 + 5; int n,m; ll a[MAX][MAX],suf[MAX][MAX],d[MAX],sum[MAX][MAX]; ll dd[MAX][MAX]; ll dp[MAX][MAX];//dp[i][j]代表前i個樹，最小等級是j的最大收益。 int main() {int t,iCase=0;cin>>t;while(t--) {scanf("%d%d",&n,&m);for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) scanf("%lld",&a[i][j]),suf[i][j] = 0,sum[i][j] = sum[i][j-1] + a[i][j];}for(int i = 1; i<=n; i++) {ll tmp = 0;suf[i][m+1] = 0;for(int j = m; j>=1; j--) tmp += a[i][j],suf[i][j] = max(suf[i][j+1],tmp);}ll ans = 0;for(int i = 1; i<=m; i++) scanf("%lld",d+i),d[i] += d[i-1];for(int i = 1; i<=n; i++) {for(int j = 1; j<=m+1; j++) {dd[i][j] = dd[i-1][j] + sum[i][m] - suf[i][j];}}for(int i = 1; i<=n; i++) {for(int j = 0; j<=m; j++) {//別忘考慮j==0的情況//如果第i個是j等級的話，那前i-1個可以隨便取ll tmp = -sum[i][j] + d[j];tmp -= dd[i-1][j+1];//for(int k = 1; k<=i-1; k++) tmp -= sum[k][m] - suf[k][j+1];dp[i][j] = tmp;if(i == 1) continue;dp[i][j] = max(tmp,dp[i-1][j] - (sum[i][m] - suf[i][j+1])); // ans = max(ans,dp[i][j]);}}for(int i = 0; i<=m; i++) ans = max(ans,dp[n][i]);printf("Case #%d: %lld\n",++iCase,ans);}return 0 ; } /* 1 2 2 -1 -1 -1 -1 -4 -4 */

?

總結

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第六场）- J】Upgrading Technology（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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