1290: 奶牛的锻炼

解题思路:

注意事项:说实话没怎么看懂！

参考代码:

#include <iostream>

using namespace std;

int main()

{    //d[i]代表第i分钟可以跑的路程

    //dp[n][m][0]代表第n分钟疲倦度为m且正在跑的路程，dp[n][m][1]就是休息时

    int n,m,dp[10001][501][2]={0};

    cin>>n>>m;

    int d[n];

    for(int i=1;i<=n;i++)cin>>d[i];

    for(int i=1;i<=n;i++)

        for(int j=0;j<=m;j++)

        {

            if(j==0)//j=0，那我必须运动哈

            dp[i][j][0]=max(max(dp[i-1][j+1][1],dp[i-1][j+1][0]),dp[i-1][j][0]);

            //dp[i-1][j+1][1]上一分钟，疲惫度为1，一直休息下来

            //dp[i-1][j+1][0]上一分钟，疲惫度为1，正在运动，现在休息下来

            //dp[i-1][j][0]上一分钟的同种情况

            else if(j==m)

            {

                dp[i][j][1]=dp[i-1][j-1][0]+d[i];

                //疲倦度满时只可能从上一分钟跑来的

            }

            else

            {

                dp[i][j][1]=max(dp[i-1][j+1][1],dp[i-1][j+1][0]);//选择休息

                //从上一分钟休息来的

                dp[i][j][0]=dp[i-1][j-1][0]+d[i];//选择运动

                //从上一分钟跑来的

            }

        }

    cout<<dp[n][0][0];

}