USACO Ski Course Design(skidesign) 题解

这一题被我想复杂了，我自己加了一个约束条件，可是题目中并没有，这个约束条件是：从high hill上砍下来的东西必须安到其他low hill上去，可是原题并没有。那么问题来了，如果加上了这个约束条件，这一题应该怎么解？

如果去掉这个约束条件，题目就变得异常简单，只需要iterate max hill的值就可以了，代码如下：

/*
ID: bbsunch2
PROG: skidesign
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
#include<fstream>
using namespace std;
int N;
int h[1001];
int main(){
    ofstream fout("skidesign.out");
    ifstream fin("skidesign.in");
    fin >> N;
    int maxHill = 0;
    for(int i = 0; i < N; ++i){
        int tempHill;
        fin >> tempHill;
        h[i] = tempHill;
        if (maxHill < tempHill) maxHill = tempHill;
    }
    int ans = 0x7FFFFFFF;
    for(int i = 0; i < maxHill; ++i){
        int tans = 0;
        for(int j = 0; j < N; ++j){
            if(h[j] < i)tans += (i - h[j]) * (i - h[j]);
            if(h[j] > i + 17)tans += (h[j] - i - 17) * (h[j] - i - 17);
        }
        ans = min(ans, tans);
    }
    cout << ans << endl;
    fout << ans << endl;
    return 0;
}