洛谷P3080 [USACO13MAR]牛跑The Cow Run

题目描述

Farmer John has forgotten to repair a hole in the fence on his farm, and his N cows (1 <= N <= 1,000) have escaped and gone on a rampage! Each minute a cow is outside the fence, she causes one dollar worth of damage. FJ must visit each cow to install a halter that will calm the cow and stop the damage.

Fortunately, the cows are positioned at distinct locations along a straight line on a road outside the farm. FJ knows the location P_i of each cow i (-500,000 <= P_i <= 500,000, P_i != 0) relative to the gate (position 0) where FJ starts.

FJ moves at one unit of distance per minute and can install a halter instantly. Please determine the order that FJ should visit the cows so he can minimize the total cost of the damage; you should compute the minimum total damage cost in this case.

农夫约翰的牧场围栏上出现了一个洞，有N(1 <= N <= 1,000)只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁，他们在外面到处搞破坏，每分钟每头牛都会给约翰带来1美元的损失。约翰必须用缰绳套住所有的牛，以停止他们搞破坏。

幸运的是，奶牛们都在牧场外一条笔直的公路上，牧场的大门恰好位于公里的0点处。约翰知道每头牛距离牧场大门的距离P_i(-500,000 <= P_i <= 500,000, P_i != 0)

约翰从农场大门出发，每分钟移动一个单位距离，每到一头牛所在的地点，约翰就会给它套上缰绳，套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少？

输入输出格式

输入格式：

Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains the integer P_i.

输出格式：

Line 1: The minimum total cost of the damage.

输入输出样例

输入样例#1：

输出样例#1：

说明

Four cows placed in positions: -2, -12, 3, and 7.

The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2 minutes for a total of 2 dollars in damage for that cow.

He then travels to position 3 (distance: 5) where the cumulative damage is 2 + 5 = 7 dollars for that cow.

He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for that cow.

Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars.

The total damage is 2 + 7 + 11 + 30 = 50 dollars.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
#define maxn 1010
int n,a[maxn],d[maxn][maxn];
long long ans=9999999999999999;
bool vis[maxn];
void dfs(int now,int cnt,long long sum){
    if(sum>ans)return;
    if(cnt==n){
        ans=min(ans,sum);
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(i,cnt+1,sum+d[now][i]*(n-cnt));
            vis[i]=0;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),d[0][i]=abs(a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=abs(a[i]-a[j]);
    dfs(0,0,0);
    cout<<ans;
}

42分暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,s[1003],f[1001][1001][2],ans;
int main(){
    freopen("Cola.txt","r",stdin);
    int i,j,k;cin>>n;
    for(i=1;i<=n;i++)cin>>s[i];
    s[i]=0;n++;
    sort(s+1,s+n+1);
    for(i=1;i<=n;i++)if(s[i]>0)break;
    k=i-1;//0的位置 
    memset(f,127/3,sizeof(f));
    f[k][k][0]=0;
    f[k][k][1]=0;
    for(i=k+1;i<=n;i++)f[k][i][0]=f[k][i-1][0]+(s[i]-s[i-1])*(n-i+k);
    for(i=k-1;i>=1;i--)f[i][k][1]=f[i+1][k][1]+(s[i+1]-s[i])*(n-k+i);
    for(i=k-1;i>=1;i--)
        for(j=k+1;j<=n;j++){
            f[i][j][1]=min(f[i+1][j][1]+(s[i+1]-s[i])*(n-j+i),f[i+1][j][0]+(s[j]-s[i])*(n-j+i));
            f[i][j][0]=min(f[i][j-1][1]+(s[j]-s[i])*(n-j+i),f[i][j-1][0]+(s[j]-s[j-1])*(n-j+i));
        }
    cout<<min(f[1][n][1],f[1][n][0])<<endl;
    return 0;
}

100分区间dp