网站开发业务怎么做,free免费空间,厦门网页设计公司价格,适合小型网络公司的建站方式可以为来源#xff1a;牛客网#xff1a;
Max Power
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld题目描述 小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有…来源牛客网
Max Power
时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
64bit IO Format: %lld题目描述 小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层第i层有n-i1个 技能每个技能只能够学习一次。除了第1层的技能可以直接学习外其他技能学习都要学习前置技能 即你要学习第i(i2)层第j列的技能那么你要先学习第i-1层的第j列和第j1列的技能。每个技能学习 后都会获得一定的战力加成。 现在小卤蛋有m个技能点一个技能点可以学习一个技能他想知道加完点后他可以获得的最大战力加成为多少。 输入描述: 有多组样例输入输入到文件结束. 每组样例第一行输入2个整数n(1n50)和m(1m1300)对应题目上的含义。 接下来共有n行第i行有n-i1个数代表这个技能学习后获得的战力加成(战力加成1000)。 输出描述: 输出最大的战力加成。 示例1 输入 复制
4 3
1 4 1 9
2 3 5
6 1
66输出 复制
15题解
我们可以看出这是个倒三角的形状。要学技能x就要学习它上面的两个技能这两个技能上面的三个技能一直推到第一层这就是一个倒三角形状也就是倒三角的内容我没必须全部学习。 我们从列的方向看会发现每一列所学的技能是一个从上往下的一个连续区间中间若有断开则最底下的技能将无法学习。其次左一列总比右一列多学一个如下 所以我们就从右向左一列一列的转移 dp[i][j][k]表示前i列一共选了k个技能学习第i列选了连续的前j个 dp[i][j][k]max(dp[i-1][p][k-j]sum[i][j]) 保证倒三角内技能全部学习 其中 sum[i][j]是列的前缀和表示第i列前j个数字的和 pj-1从j-1枚举到n-i1枚举 即第i-1列最少只比第i列少选一个最多则可以选完。 最后每个位置的dp[i][j][m]最大值为答案
代码
#includebits/stdc.h
using namespace std;
const int maxn55;
int sum[maxn][maxn];
int dp[maxn][maxn][1308];
int a[maxn];
int main()
{int n,m;while(cinnm){for(int i1;in;i){a[i]a[i-1]i;for(int j1;jn-i1;j){int x;cinx;sum[i][j]xsum[i-1][j];}}memset(dp,0,sizeof(dp));int sun0;for(int in;i;i--){for(int j0;jn-i1;j){for(int ka[j];km;k){for(int pmax(j-1,0);pn-i1;p){dp[i][j][k] max(dp[i][j][k], dp[i 1][p][k - j] sum[j][i]);}sun max(sun, dp[i][j][m]);}}}coutsunendl;}
}
