学步园

动态规划还是最无语的一块~  参见：http://zebozhuang.blog.163.com/blog/static/1714798042010107104459174/

#include<iostream><br /> #include<cstdio><br /> #include<string><br /> #include<math.h><br /> using namespace std;<br /> #define maxn 305<br /> #define maxcost 9999999<br /> int w[maxn][maxn],m[maxn][maxn],d[maxn];<br /> int min(int a,int b)<br /> {<br /> if(a>b) return b;<br /> return a;<br /> }<br /> int main()<br /> {<br /> int i,j;<br /> int v,p;<br /> cin>>v>>p;<br /> for(i=1;i<=v;i++)<br /> {<br /> scanf("%d",&d[i]);<br /> }<br /> for(i=1;i<=v;i++)<br /> for(j=1;j<=v;j++)<br /> {<br /> int mid=(i+j)/2;<br /> for(int k=i;k<=j;k++)<br /> w[i][j]+=abs(d[k]-d[mid]);<br /> }<br /> for(i=1;i<=v;i++)<br /> m[1][i]=w[1][i];<br /> for(i=2;i<=p;i++)<br /> {<br /> for(j=i;j<=v;j++)<br /> {<br /> m[i][j]=maxcost;<br /> for(int k=1;k<j;k++)<br /> {<br /> m[i][j]=min(m[i][j],m[i-1][k]+w[k+1][j]);<br /> }<br /> }<br /> }<br /> cout<<m[p][v]<<endl;<br /> return 0;<br /> }