记录编号	357080	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]架设电话线路	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.534 s
提交时间	2016-12-08 20:29:47	内存使用	39.20 MiB

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <list>
#include <vector>
using namespace std;
int dp[100001][101];
int h[100001];
inline int gval(int x)
{
    return x*x;
}
int main()
{
    freopen("phonewire.in", "r", stdin);
    freopen("phonewire.out", "w", stdout);
    int n, c;
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; i++)scanf("%d", h+i);
    memset(dp, 0xff/3, sizeof(dp));
    for(int i = 0; i <=  100; i++)dp[1][i] = gval(h[1]-i);
    for(int i = 2; i <= n; i++)
    {
        int t = 0x7ffffff;
        for(int j = 0; j <= 100; j++)
        {
            if(j >= h[i-1])t = min(t, dp[i-1][j]-j*c);
            if(j >= h[i])dp[i][j] = min(dp[i][j], t+gval(j-h[i])+j*c);
        }
        t = 0x7ffffff;
        for(int j = 100; j >= 0; j--)
        {
            if(j >= h[i-1])t = min(t, dp[i-1][j]+j*c);
            if(j >= h[i])dp[i][j] = min(dp[i][j], t+gval(j-h[i])-j*c);
        }
    }
    int t = 0x7ffffff;
    for(int i = h[n]; i <= 100; i++)t = min(t, dp[n][i]);
    printf("%d\n", t);
    return 0;
}