推荐盐城网站开发,信息系统软件有哪些,开发区网站建设在哪,怎样维护自己的网站正题
ybtoj 题目大意
给你n个时间点
在第i个时间点跑步有aia_iai点贡献#xff0c;但会加一点疲惫值#xff0c;疲惫值不能超过m
当前疲惫值为x#xff0c;那么你可以花x点时间来清空疲惫值#xff0c;当然也可以啥都不干
问你第n个时间后疲惫值为0的最大贡献 解题思…正题
ybtoj 题目大意
给你n个时间点
在第i个时间点跑步有aia_iai点贡献但会加一点疲惫值疲惫值不能超过m
当前疲惫值为x那么你可以花x点时间来清空疲惫值当然也可以啥都不干
问你第n个时间后疲惫值为0的最大贡献 解题思路
设f_{i,j}为第i个时间点疲惫值为j的最大贡献
然后按题意DP即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n, m, x, f[10010][510];
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d, x);f[i][0] f[i - 1][0];for (int j 1; j min(m, i); j)f[i][0] max(f[i][0], f[i - j][j]);//恢复体力for (int j 1; j m; j)f[i][j] max(f[i][j], f[i - 1][j - 1] x);//跑步}printf(%d, f[n][0]);return 0;
}
