d686:uva10003: Cutting Sticks

/*cost[x][y]記錄x到y的最小cost，不重複求取，若計算過就直接回傳， 有關係為cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left)， cut[i]為介於left與right的所有點， cost[][]先初始化為很大的值 ， cost[x][y]中間沒有cut，cost[x][y]=0‧ */#include <iostream>#include <algorithm>#define MAXL 1005#define MAXINT 0x7fffffffusing namespace std; int cost[MAXL][MAXL],cut[52],len,n; int min(int x,int y){ if (x>y) return y; else return x; } int dp(int left,int right){ bool found=false; if (cost[left][right] != MAXINT) return cost[left][right]; for(int i=0;i<n;i++){ if ((cut[i]>left)&&(cut[i]<right)) { found=true; cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left); } } if (found==false) cost[left][right]=0; return cost[left][right]; } int main(){ int result; while (cin >> len){ if (len == 0) break; cin >> n; for(int i=0;i<n;i++){ cin >> cut[i]; } for(int i=0;i<=len;i++) for(int j=0;j<=len;j++) cost[i][j]=MAXINT; result=dp(0,len); cout << "The minimum cutting is " << result << "." << endl; } return 0; }