BZOJ1705: [Usaco2007 Nov]Telephone Wire【DP】

dzy posted @ 2013年6月12日 21:14 in BZOJ with tags BZOJ dp , 1489 阅读










using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
Ali Backhaus 说:
2019年4月02日 14:51

Only for the telephone wire we need to use the access from the underground pipes which are safe instead of the upper level. With the including terms for the calculation while essay writing service reviews having to accelerate from the local wire to use only.

move In & move out c 说:
2021年11月15日 23:25

Some of us are rather smart and visualize doing that cleaning alone. This is finished to reduce costs which seriously isn't as substantial sum in comparison with your precious time and health and fitness. For soon after construction clean-up mess is it doesn't job connected with expert maids who realize how to clean applying cleaning apparatus and defend self on the dust.

Avatar_small 说:
2023年6月09日 17:05

We discuss, review, write and explain about different products, services, technology and more through our website which are for learning and educational purposes only. That being said, though we try to be up to date with the information, there sometimes or more can be information being outdated and any issues or problems that arise from the use of the information present on our website is solely on the users only as we try to provide this website for free in good faith only.

登录 *

loading captcha image...
or Ctrl+Enter