[USACO19OPEN]Snakes

古城微笑少年丶 2023-06-01 06:09 1阅读 0赞

**题面：**

> 传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
> 
> Bessie装备了一个捕网，用来捕捉 NN 组排成一行的蛇（ 1 \\leq N \\leq 4001≤N≤400 ）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
> 
> 一个大小为 ss 的捕网意味着Bessie可以抓住任意包含 gg 条的一组蛇，其中 g \\leq sg≤s 。然而，每当Bessie用大小为 ss 的捕网抓住了一组 gg 条蛇，就意味着浪费了 s-gs−g 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 KK 次捕网大小（ 1 \\leq K<N1≤K<N ）。
> 
> 请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

显然是DP......

然而考场写了个假算法，$O(n^3\*m)$的DP，而且毒瘤出题人并没有具体的数据范围，只给了一个n<=400...

考场上$O(n^3\*m)$的算法拿了48pts；

由于常数的问题是所有打部分分的人里面得分最高的；

然而出考场用了毒瘤方法卡常后拿了70+pts(在Luogu上甚至拿了80pts)

**先贴个假算法：**

令$f\[i\]\[j\]\[k\]$表示当前在抓第$i$堆蛇，从$i$开始到$i+j-1$堆蛇都用一种背包大小抓，已经用了k个蛇袋子；

显然这里要用$\[i,i+j-1\]$中的最大值来抓这个区间内所有的蛇；

不难得到转移方程：$$f\[i\]\[j\]\[k\]=min\\\{f\[p\]\[i-p\]\[k-1\]\\\}+Max(i,i+j-1)\*j-(sum\[i+j-1\]-sum\[i-1\])$$

其中$Max(l,r)$表示区间$\[l,r\]$中$a\[\]$的最大值，$sum\[i\]$为$a\[\]$的前缀和

但是——考试的时候毒瘤出题人还卡了空间...

于是乎我们观察到$f\[i\]\[j\]\[k\]$中的状态$k$只与$k-1$有关，所以把第三维压掉即可

（代码写的有点难以描述，但是反正是假算法，将就一下呗）

1 #include<bits/stdc++.h>
     2 #define int long long
     3 using namespace std;
     4 inline int read(){
     5     int ans=0,f=1;char chr=getchar();
     6     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     7     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     8     return ans*f;
     9 }const int M = 405;
    10 int f[M][M][2],a[M],n,K,s[M],g[M][M];
    11 signed main(){
    12     n=read(),K=read();
    13     for(int i=1;i<=n;i++)a[i]=read(),s[i]=a[i]+s[i-1];
    14     for(int len=1;len+1-1<=n;len++){
    15         int maxn=0;
    16         for(int i=1;i<=len;i++) maxn=max(maxn,a[i]);
    17         g[1][len]=maxn*len-s[len];
    18     }memset(f,0x3f,sizeof(f));
    19     for(int k=1;k<=K;k++)
    20         for(int i=k+1;i<=n;i++)
    21             for(int j=1;j<=n-i+1;j++){
    22                 int maxn=0;
    23                 for(int p=i;p<=i+j-1;p++)maxn=max(maxn,a[p]);
    24                 f[i][j][k&1]=g[1][i-1];
    25                 for(int p=2;p<i;p++){
    26                     if(k-1==0&&p!=1) continue;
    27                     f[i][j][k&1]=min(f[p][i-p][k&1^1],f[i][j][k&1]);
    28                 }f[i][j][k&1]+=maxn*j-s[i+j-1]+s[i-1];
    29             }int ans=0x7f7f7f7f7f;
    30     for(int i=K+1;i<=n;i++)ans=min(ans,f[i][n-i+1][K&1]);
    31     cout<<ans<<endl;
    32     return 0;
    33 }

考虑优化这个算法：

**方法一：**

**智商不够，数据结构来凑**

因为转移的时候枚举的是$f\[p\]\[i-p\]\[k-1\]$，也就是说我们的第一维状态和第二维状态之间其实是线性关系（因为在一次转移过程中$i$的值是确定的），所以我们可以考虑用线段树来优化这个枚举$p$的过程，然后求$a\[\]$数组一段的最大值我们可以用线段树，也可以用st表，也可以直接O(n^3)预处理

时间复杂度$O(n^2mlogn)$

因为跑不满所以理论上可以过，然而由于线段树自带大常数，所以并不推荐（其实我也没试过）

**方法二：**

其实我们的状态设计的并不是很好，因为$f\[i\]\[j\]\[k\]$的状态设计已经潜在的要求了我们枚举$i,j$两个状态，我们能不能通过改变状态来减少枚举的维度呢？

显然是可以的，因为$f\[i\]\[j\]\[k\]$中只有$j$这个状态看着十分鸡肋，因为状态$i$显然是必须的，而状态$k$是只与$k-1$有关的，所以不用管它们；

根据这个思路，我们重新设计状态，设$f\[i\]\[j\]$表示前面$i$个已经处理好了，并且已经用了j张网

不难拿到方程：$$f\[i\]\[j\]=Min\\\{f\[k\]\[j-1\]+Max(k+1,i)\*(i-k)-(sum\[i\]-sum\[k\])\\\}$$

其中Max我们用st表预处理然后O(1)求就好了

老年选手并不打算卡常......所以就贴一个正常的代码惹qwq

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 inline int read(){
     4     int ans=0,f=1;char chr=getchar();
     5     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     6     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     7     return ans*f;
     8 }const int M = 405;
     9 int st[M][15],n,a[M],m,p[20],f[M][M],s[M],lg2[M]={-1};
    10 #define min(x,y) ((x)>(y)?(y):(x))
    11 #define max(x,y) ((x)<(y)?(y):(x))
    12 inline int Max(int l,int r){
    13     int px=lg2[r-l+1];
    14     return max(st[l][px],st[r-p[px]+1][px]);
    15 }
    16 int main(){
    17     freopen("snakes.in","r",stdin);
    18     freopen("snakes.out","w",stdout);
    19     n=read(),m=read(),p[0]=1;
    20     for(register int i(1);i<=n;++i)a[i]=read(),st[i][0]=a[i],s[i]=s[i-1]+a[i],lg2[i]=lg2[i>>1]+1;
    21     for(register int j(1);j<=14;p[j]=p[j-1]<<1,++j)
    22         for(register int i(1);i<=n;++i)
    23             st[i][j]=max(st[i][j-1],st[i+p[j-1]][j-1]);
    24     for(register int i(1);i<=n;++i)f[i][0]=Max(1,i)*i-s[i];
    25     for(register int i(2);i<=n;++i)
    26         for(register int j(1);j<=min(i-1,m);++j){
    27             f[i][j]=0x3f3f3f3f;
    28             for(register int k(1);k<i;++k)
    29                 f[i][j]=min(f[k][j-1]+Max(k+1,i)*(i-k)-s[i]+s[k],f[i][j]);
    30         }printf("%d\n",f[n][m]);
    31     return 0;
    32 }

转载于:https://www.cnblogs.com/zhenglw/p/11508869.html