这题的关键在于想到怎么dp，及怎样去描述一个状态。

首先想到dp[i]表示到达i位置的最小疲劳值，但发现这样不太对，因为这样的话不好转移（因为转移的时候我们需要知道拿着哪把伞走过一格）；因此想到dp[i][j]表示走到i点拿着j雨伞的最小疲劳值。这样的话怎么转移呢

如果这个格子上有j雨伞，那说明j雨伞就是在i这个位置上拿的 dp[i][j] = min( dp[i][j],dp[i-1][k]+id[k] ) 【k=0-m】 //j=0时代表不拿伞, id[i]代表i雨伞的重量

如果没有j雨伞，那说明在到达i点前就拿到j雨伞了 dp[i][j] = dp[i-1][j] + id[j]

那转移方程写完了，最后考虑边界条件。

1.在起点

2.在雨里但j=0

 

以上

===2018.9.5===

这次想了一下时间复杂度，乍一看是a*m*m的复杂度会tle。（因为有a*m个状态；然后如果点i上有j这把雨伞的话那要m的代价转移，不然O(1)转移）

但实际上它的复杂度就是a*m，因为不会每个状态都要m代价转移。（因为只有m把雨伞，最多只有m个状态要花m的代价去转移。）

所以就过了。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define INF 2100000000 6 using namespace std; 7  8 int rain[2005],id[2005];//id[i]代表编号为i的雨伞的重量 9 vector
         
           umb[2005];//每个位置上可能有多个雨伞 10 int memo[2005][2005];//dp[i][j]代表拿着j雨伞走到i点【此时换完伞准备出发】的最小疲劳值,j=0代表不拿伞11 12 int main(){13     int a,n,m; cin>>a>>n>>m;14     for(int i=1;i<=n;i++){15         int l,r; cin>>l>>r;16         for(int j=l;j
          
           >x>>p;21 umb[x].push_back(i);22 id[i]=p;23 }24 25 for(int i=0;i<=a;i++){26 for(int j=0;j<=m;j++){27 bool contain=false;28 for(int k=0;k