代理记账 营销型网站,商标图案大全大图 logo,中国有几大电商平台,wordpress仿站步奏UVA_10003 这是个区间的动态规划问题#xff0c;首先我们可以补两个端点#xff0c;然后就按区间长度递增的顺序进行递推即可#xff0c;区间长度为1时的花费要初始化成0#xff0c;其余初始化为INF。 转移方程为f[i, j] min{f[i, k] f[k, j] a[j] – a[i]}(i k 首先我们可以补两个端点然后就按区间长度递增的顺序进行递推即可区间长度为1时的花费要初始化成0其余初始化为INF。 转移方程为f[i, j] min{f[i, k] f[k, j] a[j] – a[i]}(i k j)。 #includestdio.h#includestring.h#define MAXD 60#define INF 100000000int a[MAXD], N, L, f[MAXD][MAXD];int init(){int i, j; scanf(%d, L);if(!L)return 0; scanf(%d, N); a[0] 0, a[N 1] L;for(i 1; i N; i ) scanf(%d, a[i]);return 1;}void solve(){int i, j, n, p, temp; n N 1;for(i 0; i n; i )for(j i 1; j n; j ) {if(i 1 j) f[i][j] 0;else f[i][j] INF; }for(p 2; p n; p )for(i 0; i p n; i )for(j i 1; j i p; j ) { temp f[i][j] f[j][i p] a[i p] - a[i];if(temp f[i][i p]) f[i][i p] temp; } printf(The minimum cutting is %d.\n, f[0][n]);}int main(){while(init()) { solve(); }return 0;} 转载于:https://www.cnblogs.com/staginner/archive/2011/11/03/2234716.html
