【BZOJ1150】数据备份（动态规划，凸优化）

题面

题解

在不考虑\(K\)的情况下很容易\(dp\)

如果把\(K\)考虑进状态显然是\(O(n^2)\)级别。

所以凸优化一下即可。

注意一下是一个下凸函数，所以是没操作一次就要减去一个权值。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long long#define MAX 100100inline ll read(){ ll x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int n,K;ll s[MAX];struct Node{ll x,y;}f[2][MAX];Node operator+(Node a,int b){return (Node){a.x+b,a.y};}bool operator<(Node a,Node b){return a.x
          
           >1; calc(mid); if(f[0][n].y<=K)l=mid+1,ans=f[0][n].x+K*mid; else r=mid-1; } printf("%lld\n",ans); return 0;}