题目大意:
农夫约翰的牧场围栏上出现了一个洞, 有 N(1 <= N <= 1,000)只牛从这个洞逃出了牧场. 这些出逃的奶牛很狂躁, 他们在外面到处搞破坏, 每分钟每头牛都会给约翰带来 1 美元的损失. 约翰必须用缰绳套住所有的牛, 以停止他们搞破坏.
幸运的是, 奶牛们都在牧场外一条笔直的公路上, 牧场的大门恰好位于公里的 0 点处. 约翰知道每头牛距离牧场大门的距离 P_i(-500,000 <= P_i <= 500,000, P_i != 0)
约翰从农场大门出发, 每分钟移动一个单位距离, 每到一头牛所在的地点, 约翰就会给它套上缰绳, 套缰绳不花时间. 按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少?
区间 DP
关键在于处理, 其实也挺简单的
设状态 $f[i][j][0]$ 表示覆盖了区间 $(i,j)$ 当前点在 $j$ 的最小值,$f[i][j][1]$ 表示覆盖了区间 $(i,j)$ 当前点在 $i$ 的最小值
状态转移方程为
$f[i][j][0]=min(f[i][j-1][1]+(p[j]-p[i])*(n-j+i),f[i][j-1][0]+(p[j]-p[j-1])*(n-j+i))$
区间 $(i,j)$ 且当前点在 $j$ 由区间 $(i,j-1)$FJ 位于 $i$ 向 $j$ 跳和区间 $(i,j-1)$ 位于 $j-1$ 向 $j$ 跳
$f[i][j][1]=min(f[i+1][j][1]+(p[i+1]-p[i])*(n-j+i),f[i+1][j][0]+(p[j]-p[i])*(n-j+i))$
区间 $(i,j)$ 且当前点在 $i$ 由区间 $(i+1,j)$FJ 位于 $i+1$ 向 $i$ 跳和区间 $(i+1,j)$ 位于 $j$ 向 $i$ 跳
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<algorithm>
- #include<cstring>
- #define N 1006
- using namespace std;
- int n,p[N],f[N][N][2];
- //f[i][j][0]套完区间 i,j 且当前点在 j 的最小代价
- //f[i][j][1]与此相反
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%d",&p[i]);
- p[++n]=0;
- sort(p+1,p+n+1);
- int s;
- for(int i=1;i<=n;i++) if(!p[i]) {s=i;break;}
- memset(f,0x3f,sizeof(f));
- f[s][s][0]=f[s][s][1]=0;
- for(int i=s+1;i<=n;i++)
- f[s][i][0]=f[s][i-1][0]+(p[i]-p[i-1])*(n-i+s);// 上一个的损失 + 距离 * 还未选择的奶牛 (已经选了(i-s+1), 共 n(n+1) 头奶牛, so 还未选(n-i+s))
- for(int i=s-1;i>=1;i--)
- f[i][s][1]=f[i+1][s][1]+(p[i+1]-p[i])*(n-s+i);// 上一个奶牛的损失 + 距离 * 还未选择的奶牛 (已经选了(s-i+1), 共 n(n+1) 头, so 还未选(n-s+i))
- for(int i=s-1;i>=1;i--){
- for(int j=s+1;j<=n;j++){
- f[i][j][1]=min(f[i+1][j][1]+(p[i+1]-p[i])*(n-j+i),f[i+1][j][0]+(p[j]-p[i])*(n-j+i));
- f[i][j][0]=min(f[i][j-1][1]+(p[j]-p[i])*(n-j+i),f[i][j-1][0]+(p[j]-p[j-1])*(n-j+i));
- }
- }
- printf("%d",min(f[1][n][1],f[1][n][0]));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2766767.html