POJ 3661-Running（DP） - c++编程基础

题目链接：点击打开链接

题意：在一条直线上运动，每分钟可以运动距离a[i] ,每分钟可以选择运动或者休息，有一个疲劳系数，最初为0，每运动一分钟疲劳系数加1,（不能大于m）同理，每休息一分钟，疲劳系数减1，（不能小于0）求n分钟后最大运动距离，要求n分钟时疲劳系数要为0.

两个状态，当前时间及当前疲劳系数。设 dp[i][j] =dp[i-1][j-1]+a[i] (j>0) else dp[i][j] =max(dp[i][j],max(dp[i-k][0],dp[i-k][k]) ) (k<=m&&k

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 1<<12 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair
               
                 #define ull unsigned long long using namespace std; int dp[10002][502],n,m,a[10002]; void solve() { memset(dp,0,sizeof(dp)); dp[1][0]=0;dp[1][1]=a[1]; for(int i=2;i<=n;i++) { for(int j=0;j<=m;j++) { if(j==0) { int tem=-1; for(int k=0;k<=m&&k
                
                 记忆化不太好写。。不写了~~