DP+滚动数组 || [Usaco2007 Nov]Telephone Wire 架设电话线 || BZOJ 1705 || Luogu P2885

本来是懒得写题解的…想想还是要勤发题解和学习笔记…然后就滚过来写题解了。

题面：[USACO07NOV]电话线Telephone Wire

题解：

F[ i ][ j ] 表示前 i 根电线杆，第 i 根电线杆长度为 j 时的最优答案

容易推出基本的转移方程：

mx为初始最长的电线杆长度，显然延长后的电线杆最长不会超过mx

然后就把绝对值拆开，分类讨论一下

然后就发现这个东西可以单调队列优化DP，但是这个题目并不需要单队优化，在循环时记录一下最大值就可以

然后因为给的空间就64MB，所以要套一个滚动数组

就这样了…啊写题解好累啊

代码：

 #include<cstdio>

 #define max(a,b) ((a)>(b)?(a):(b))

 #define min(a,b) ((a)<(b)?(a):(b))

 #define sqr(a) ((a)*(a))

 using namespace std;

 const int maxn=1e5+,inf=<<,maxh=;

 int N,C,H[maxn],F[][maxh],mx=,ans=inf;

 int main(){

     scanf("%d%d",&N,&C);

     for(int i=;i<=N;i++) scanf("%d",&H[i]),mx=max(mx,H[i]);

     for(int i=;i<=mx;i++) F[][i]=F[][i]=inf;

     for(int i=H[];i<=mx;i++) F[][i]=sqr(i-H[]);

     for(int i=;i<=N;i++){

         int k=inf;

         for(int j=H[i-];j<=mx;j++){

             k=min(k,F[(i-)&][j]-C*j);

             if(j>=H[i]) F[i&][j]=k+j*C+sqr(j-H[i]);

         }

         k=inf;

         for(int j=mx;j>=H[i];j--){//

             k=min(k,F[(i-)&][j]+C*j);

             F[i&][j]=min(F[i&][j],k-j*C+sqr(j-H[i]));

         }

         for(int j=;j<=mx;j++) F[(i+)&][j]=inf;

     }

     for(int i=H[N];i<=mx;i++) ans=min(ans,F[N&][i]);

     printf("%d\n",ans);

     return ;

 }

---

By:AlenaNuna