网站开发的关键计算机资源计划,云商城是什么,江西省建设招标网站,成都建立公司网站题目 1613: [Usaco2007 Jan]Running贝茜的晨练计划 Time Limit: 5 Sec Memory Limit: 64 MBDescription 奶牛们打算通过锻炼来培养自己的运动细胞#xff0c;作为其中的一员#xff0c;贝茜选择的运动方式是每天进行N(1 N 10,000)分钟的晨跑。在每分钟的开始… 题目 1613: [Usaco2007 Jan]Running贝茜的晨练计划 Time Limit: 5 Sec Memory Limit: 64 MB Description 奶牛们打算通过锻炼来培养自己的运动细胞作为其中的一员贝茜选择的运动方式是每天进行N(1 N 10,000)分钟的晨跑。在每分钟的开始贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地如果贝茜选择在第i分钟内跑步她可以在这一分钟内跑D_i(1 D_i 1,000)米并且她的疲劳度会增加 1。不过无论何时贝茜的疲劳度都不能超过M(1 M 500)。如果贝茜选择休息那么她的疲劳度就会每分钟减少1但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话疲劳度不会再变动。晨跑开始时贝茜的疲劳度为0。 还有在N分钟的锻炼结束时贝茜的疲劳度也必须恢复到0否则她将没有足够的精力来对付这一整天中剩下的事情。 请你计算一下贝茜最多能跑多少米。 Input * 第1行: 2个用空格隔开的整数N 和 M * 第2..N1行: 第i1为1个整数D_i Output * 第1行: 输出1个整数表示在满足所有限制条件的情况下贝茜能跑的最大 距离 Sample Input 5 2 5 3 4 2 10 Sample Output 9 输出说明: 贝茜在第1分钟内选择跑步跑了5米在第2分钟内休息在第3分钟内跑 步跑了4米剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须 为0所以她不能在第5分钟内选择跑步。 题解 这道题一开始用主动转移竟然Wa了为了珍惜提交次数我还是写了被动转移。f[i][j]表示i分钟j的疲劳能做到的最大距离。 方程 f[i][j]max(f[i][j],f[i-1][j-1]di[i]) f[i][0]max(f[i][0],f[i-j][j]) 代码 /*Author:WNJXYK*/
#includecstdio
#includeiostream
#includecstring
#includestring
#includealgorithm
#includequeue
#includeset
#includemap
using namespace std;#define LL long long
#define Inf 2147483647
#define InfL 10000000000LLinline void swap(int x,int y){int tmpx;xy;ytmp;}
inline void swap(LL x,LL y){LL tmpx;xy;ytmp;}
inline int remin(int a,int b){if (ab) return a;return b;}
inline int remax(int a,int b){if (ab) return a;return b;}
inline LL remin(LL a,LL b){if (ab) return a;return b;}
inline LL remax(LL a,LL b){if (ab) return a;return b;}int n,m;
int di[10005];
int f[10005][505];
int main(){scanf(%d%d,n,m);for (int i1;in;i) scanf(%d,di[i]);memset(f,-127,sizeof(f));f[0][0]0;for (int i1;in;i){f[i][0]f[i-1][0];for (int j1;jm;j){if (ji) f[i][0]remax(f[i][0],f[i-j][j]);f[i][j]remax(f[i][j],f[i-1][j-1]di[i]);}}printf(%d\n,f[n][0]);return 0;
}转载于:https://www.cnblogs.com/WNJXYK/p/4063926.html
