是在區(qū)間DP里面看到這道題目的，于是想用區(qū)間DP弄一弄，但是考慮到10000×10000的數(shù)組而且我還不會(huì)平行四邊形優(yōu)化，只能拿到n3的復(fù)雜度，于是就放棄了區(qū)間DP的做法

        思考了大約10分鐘，發(fā)現(xiàn)根本不用區(qū)間DP嘛，定義狀態(tài)dp[i][j]表示第i分鐘疲勞度為j時(shí)走的最遠(yuǎn)距離，狀態(tài)轉(zhuǎn)移方程一下就出來了，可以選擇走或者休息

        采用了刷表法1A，但是看見網(wǎng)上的很多都沒用刷表法寫嘛

        judge[i][j]表示狀態(tài)[i][j]是否有效

        每一個(gè)狀態(tài)[i][j]可以更新到3個(gè)位置，一個(gè)是[i+1][j+1](j<m)，一個(gè)是[i+j][0](i+j<=n)，一個(gè)是[i+1][0](j==0)

        不是很難，就不放到100道里面去了

#include <iostream>#include <cstring>#include <algorithm>using namespace std;int dp[10005][505],n,m,d[10005];bool judge[10005][505],t=true;int main(){    ios_base::sync_with_stdio(false);    while(cin>>n>>m){        for(int i=1;i<=n;++i)            cin>>d[i];        dp[0][0]=0;        judge[0][0]=t;        for(int i=0,limi=min(i,m);i<n;limi=min(++i,m))        for(int j=0;j<=limi;++j)        if(judge[i][j]==t){            if(j<m&&(judge[i+1][j+1]!=t||dp[i+1][j+1]<dp[i][j]+d[i+1]))                judge[i+1][j+1]=t,dp[i+1][j+1]=dp[i][j]+d[i+1];            if(i+j<=n&&(judge[i+j][0]!=t||dp[i+j][0]<dp[i][j]))                judge[i+j][0]=t,dp[i+j][0]=dp[i][j];            if(j==0&&(judge[i+1][0]!=t||dp[i+1][0]<dp[i][j]))                judge[i+1][0]=t,dp[i+1][0]=dp[i][j];        }        cout<<dp[n][0]<<endl;        t^=1;    }}