BZOJ1705: [Usaco2007 Nov]Telephone Wire【DP】

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

设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}(k是第i-1位上的数,j是当前位上的数)

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试?

j>k时:dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时:dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k},g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话,第一维好像一点用都没有。那就不要了!

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
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();
    memset(dp,63,sizeof(dp));
    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]);
        memset(dp,63,sizeof(dp));
        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;
}
Avatar_small
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.

Avatar_small
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
networkslog.com 说:
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 networkslog.com 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