[USACO07NOV] Telephone Wire G

dp题，做法有点套路但是一开始没想到。
设 \(dp{_i}_j\) 表示第 \(i\) 位为 \(j\) 的最小花费。
然后直接往下转移就好了。

点击查看代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back 
#define p_b push_back
#define il inline
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=1e5+1;
int n;
ll a[N],h,dp[N][101],ans=1e18,c;
signed main(){ios;cin>>n>>c;for(int i=1;i<=n;i++){cin>>a[i];h=max(h,a[i]);}for(int i=1;i<=n;i++)for(int j=1;j<=h;j++)dp[i][j]=1e18;for(int i=a[1];i<=h;i++){ll w=(i-a[1])*(i-a[1]);dp[1][i]=w;}for(int i=2;i<=n;i++)for(int j=a[i];j<=h;j++)for(int k=a[i-1];k<=h;k++){ll w=(j-a[i])*(j-a[i]);dp[i][j]=min(dp[i][j],dp[i-1][k]+w+c*abs(j-k));}for(int i=a[n];i<=h;i++)ans=min(dp[n][i],ans);cout<<ans;return 0;
}