首页 > 代码库 > 【POJ3612】【USACO 2007 Nov Gold 】1.Telephone Wire 动规
【POJ3612】【USACO 2007 Nov Gold 】1.Telephone Wire 动规
题意:
给出若干棵树的高度,你可以进行一种操作:把某棵树增高h,花费为h*h。
操作完成后连线,两棵树间花费为高度差*定值c。
求两种花费加和最小值。
题解:
跟NOIP2014 D1T3很像。
暴力动规是O(1*10^9)会T
所以单调队列一下,每颗树扫两遍结束。
完事,看水代码吧。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101000 #define M 105 #define inf 0x3f3f3f3f using namespace std; int f[2][M],g[2][M],n,c; int now,last; int h[N]; int main() { // freopen("test.in","r",stdin); int i,j,k; scanf("%d%d",&n,&c); for(i=1;i<=n;i++)scanf("%d",&h[i]); now=0,last=1; for(i=1;i<=n;i++) { now^=1,last^=1; int temp=inf; for(j=100;j>=h[i];j--) { temp=min(temp+c,f[last][j]); f[now][j]=temp+(j-h[i])*(j-h[i]); } temp=inf; for(j=1;j<=100;j++) { temp=min(temp+c,f[last][j]); f[now][j]=min(f[now][j],temp+(j-h[i])*(j-h[i])); if(j<h[i])f[now][j]=inf; } } int ans=inf; for(i=1;i<=100;i++)ans=min(ans,f[now][i]); printf("%d\n",ans); return 0; }
【POJ3612】【USACO 2007 Nov Gold 】1.Telephone Wire 动规
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。