single inpu cst class pac ios 不等式 lang rep
Input
Output
Sample Input
- 10 5
- 1 2 3 6 7 9 11 22 44 50
Sample Output
- 9
n个绿色点选m个染成红点,使得每个点到最近的红点距离和最小;
划分区间的时候,c[i][j]的为i到j染一个点的最优解(很好的思想)。
暴力的DP:
- #include<cstdio>
- #include<cstdlib>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- using namespace std;
- const int inf=1000000000;
- const int maxn=330;
- int sum[maxn],a[maxn],dp[maxn][33];
- int c[maxn][maxn];
- int main()
- {
- int n,m,i,j,k;
- scanf("%d%d",&n,&m);
- for(i=1;i<=n;i++) scanf("%d",&a[i]);
- for(i=1;i<=n;i++)
- for(j=1;j<=m;j++) dp[i][j]=inf;
- sort(a+1,a+n+1);
- for(i=1;i<=n;i++)
- for(j=i+1;j<=n;j++){
- int mid=(i+j)/2;
- for(k=i;k<=j;k++)
- c[i][j]+=abs(a[k]-a[mid]);
- }
- for(i=1;i<=n;i++) dp[i][1]=c[1][i];
- for(i=2;i<=n;i++)
- for(j=2;j<=m;j++){
- for(k=1;k<i;k++)
- dp[i][j]=min(dp[i][j],dp[k][j-1]+c[k+1][i]);
- }
- printf("%d\n",dp[n][m]);
- return 0;
- }
优化的DP:
- #include < cstdio > #include < cstdlib > #include < iostream > #include < algorithm > #include < cstring > #include < cmath > using namespace std;
- const int inf = 1000000000;
- const int maxn = 330;
- int sum[maxn],
- a[maxn],
- dp[33][maxn];
- int c[maxn][maxn],
- s[maxn][maxn];
- int main() {
- int n,
- m,
- i,
- j,
- k;
- scanf("%d%d", &n, &m);
- for (i = 1; i <= n; i++) scanf("%d", &a[i]);
- for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) dp[i][j] = inf;
- sort(a + 1, a + n + 1);
- for (i = 1; i <= n; i++) for (j = i; j <= n; j++) {
- int mid = (i + j) / 2;
- for (k = i; k <= j; k++) c[i][j] += abs(a[k] - a[mid]);
- }
- for (i = 1; i <= n; i++) dp[1][i] = c[1][i];
- for (i = 2; i <= m; i++) {
- s[i][n + 1] = n;
- for (j = n; j >= 1; j--) {
- for (k = s[i - 1][j]; k <= s[i][j + 1]; k++) {
- if (dp[i][j] > dp[i - 1][k] + c[k + 1][j]) {
- s[i][j] = k;
- dp[i][j] = dp[i - 1][k] + c[k + 1][j];
- }
- }
- }
- }
- printf("%d\n", dp[m][n]);
- return 0;
- }
POJ1160 Post Office (四边形不等式优化DP)
single inpu cst class pac ios 不等式 lang rep
原文:http://www.cnblogs.com/hua-dong/p/7819612.html
来源: http://www.bubuko.com/infodetail-2391052.html