Uva 10003-Cutting Sticks（区间DP） - c++编程基础

题目链接：点击打开链接

题意：一根长度为L 的木棒，要求要切割n次，给出n次需要切割的位置，每次切割花费为当前段的总长度。求最小花费。

思路：。。一开始想了好久也没往区间DP那方面想QAQ。设 dp[i][j] 为切割[i,j] 区间的最小花费，状态转移方程为 dp[i][j]=max(dp[i][k-1]+dp[k+1][j]+a[j+1]-a[i-1]);

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair
               
                 #define ull unsigned long long using namespace std; int a[55],L,dp[55][55],n; int dfs(int l,int r) { int& ans=dp[l][r]; if(ans>=0)return ans; if(l==r) return ans=a[r+1]-a[l-1]; if(l>r)return ans=0; ans=INF; for(int i=l;i<=r;i++) ans=min(ans,dfs(l,i-1)+dfs(i+1,r)+a[r+1]-a[l-1]); return ans; } int main() { while(~scanf("%d",&L)&&L) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[0]=0;a[n+1]=L; memset(dp,-1,sizeof(dp)); printf("The minimum cutting is %d.\n",dfs(1,n)); } return 0; }