POJ3661Running 문제 해결 동적 계획 DP

Running
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 3129
 
Accepted: 1073
Description
The cows are trying to become better athletes, so Bessie is running on a track for exactly N (1 ≤ N ≤ 10,000) minutes. During each minute, she can choose to either run or rest for the whole minute.
The ultimate distance Bessie runs, though, depends on her 'exhaustion factor', which starts at 0. When she chooses to run in minute i, she will run exactly a distance of Di (1 ≤ Di ≤ 1,000) and her exhaustion factor will increase by 1 -- but must never be allowed to exceed M (1 ≤ M ≤ 500). If she chooses to rest, her exhaustion factor will decrease by 1 for each minute she rests. She cannot commence running again until her exhaustion factor reaches 0. At that point, she can choose to run or rest.
At the end of the N minute workout, Bessie's exaustion factor must be exactly 0, or she will not have enough energy left for the rest of the day.
Find the maximal distance Bessie can run.
Input
* Line 1: Two space-separated integers: N and M* Lines 2..N+1: Line i+1 contains the single integer: Di
Output
* Line 1: A single integer representing the largest distance Bessie can run while satisfying the conditions.　
Sample Input

5 2
5
3
4
2
10

Sample Output

9

Source
USACO 2008 January Silver
 
 
상태:
d[i][j]는 전 i분 피로치가 j일 때 최대치를 나타낸다
 
상태 이동 방정식:
d[i][j]=d[i-1][j-1]+a[i]     
d[i][0]=max{d[i-j][j]} j<=m&&j 
코드:
  #include #define max(a,b) ((a)>(b)?(a):(b)) int a,d[100005][505],n,m,i,j; intmain() {scanf('%d%d', &n, &m); for(i=1;i<=n;i++) {scanf('%d', &a); d[i][0]=d[i-1][0]; for(j=1;j<=m;j+) {if(j공식 문제 를 첨부 하다
USACO JAN08 Problem 'cowrun' Analysis by Neal Wu This is a straightforward dynamic programming (DP) problem. To solve the problem, we want to find, for each k such that 0 <= k <= N, the maximum possible distance Bessie could have run after the first k minutes, if she has a rest factor of 0. (For example, if we can obtain a distance of 14 after 5 minutes with a rest factor of 0, or we can obtain a distance of 15 after 5 minutes with a rest factor of 0, we would always choose the second over the first.) Clearly, the best such value for 0 is 0. Then, for each minute i of the N minutes, we can compute all of the next values possible with the following method: -First, try to not run during the minute, and see if this produces an improvement. (Thus, check if the best value for i is better than the one for i + 1.) -Then, for each number k from 1 to M, let Bessie run for exactly k minutes and then rest for k minutes. See if this new value produces a greater value than the best value for i + 2k (which is the number of minutes finished after running for k minutes and resting for another k minutes). Thus, since we do M updates for each of the N minutes, our total complexity is O(NM). The following is a sample solution: #include int N,M,i,j,dist[10005],best[10005]; int main () { scanf("%d%d",&N,&M); for(i=0;ibest[i+1]) best[i+1]=best[i]; int sum=best[i],pos=i; for(j=0;jbest[pos]) best[pos]=sum; } } printf("%d/n",best[N]); }