绕了我好久,想了很多不是很顺利,DP题目思路太活络,花了好几个小时,后来参考了很多人的想法,都说是入门级DP,可是觉得好难,dp数组一开始就没设定好,最后以dp[i][j]来表示 区间 i到j的最小花费就可以了,
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; // int len; int l[1000 + 5]; int dp[1005][1005]; int n; void clear() { memset(l,0,sizeof(l)); memset(dp,-1,sizeof(dp)); } int caldp(int x,int y) { if(dp[x][y] != -1) return dp[x][y]; dp[x][y] = inf; bool flag = false; for(int i=0;i<n;i++) if(l[i] >x && l[i] < y) { flag = true; dp[x][y] = min(caldp(x,l[i]) + caldp(l[i],y) + (y - x),dp[x][y]); } if(!flag) dp[x][y] = 0; return dp[x][y]; } int main() { while(scanf("%d",&len),len) { clear(); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&l[i]); caldp(0,len); printf("The minimum cutting is %d.\n",dp[0][len]); } return EXIT_SUCCESS; }