[USACO08FEB]修路Making the Grade 动态规划

对的\(n^3\)的程序调了一个月了，惊了。。。

HSZ学oi\(\Longleftrightarrow\)闭眼学oi

要不是翻旧账还看不见。。

这是有\(n^2\)做法的。

参见LYD的书P244

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<cstdio>

#define abs absl

using namespace std;

int n;

long long absl(long long x) {

    if(x>0)return x;

    return -x;

}

long long a[2005],b[2005],c[2005],f[2005][2005];

long long ans=0x3f3f3f3f3f3f3f3f,cnt;

int main() {

	freopen("testdata.in","r",stdin);

    cin>>n;

    for(int i=1; i<=n; i++) {scanf("%lld",&a[i]);c[++cnt]=a[i];}

    sort(c+1,c+1+cnt);

    for(int i=1; i<=n; i++) {

    	long long tp=f[i-1][1];

        for(int j=1; j<=n; j++) {

        	tp=min(tp,f[i-1][j]);

        	f[i][j]=abs(a[i]-c[j])+tp;

        }

    }

    for(int i=1; i<=n; i++)

        ans=min(f[n][i],ans);

    cout<<ans;

    return 0;

}

巴特西

[USACO08FEB]修路Making the Grade 动态规划

最新文章

热门文章