[loj3313]序列

定义$C_{i}$表示令$i,i+1,i+2,...$的位置减1的操作，定义$I_{i}$表示令$i,i+2,i+4,...$的位置减1的操作

结论1：一定存在一种最优解使得$\forall i$不同时存在$I_{i}$和$I/C_{i+1}$操作（用其他操作等效替代即可证明）

结论2：当$a_{1},a_{2}>0$时，一定存在一种最优解使得其中一次执行了一次$C_{1}$操作（结论1的简单推论）

根据上述结论进行贪心，记录$(a,b,c)$表示可以免费进行$a$次$C_{i}$操作、$b$次$I_{i}$操作和$c$次$I_{i+1}$操作

对于每一个位置，优先使用免费操作，按以下方式选择免费操作：

1.若$a+b\le a_{i}$，将这$a+b$次操作全部执行

2.若$a+b>a_{i}$，相当于要确定$x+y=a_{i}$，其中$0\le x\le a$且$0\le y\le b$

观察到$a_{i}-b\le x\le a$且$a_{i}-a\le y\le b$，那么必然要执行$a_{i}-b$次$C_{i}$操作和$a_{i}-a$次$I_{i}$操作

（这里有一个小问题：为了让次数为非负数，需要让$a$和$b$对$a_{i}$取min，这样显然不影响答案）

对于剩下的免费操作，这些免费操作的意义就是让答案减小$a_{i}'$，因此直接令答案减小$a_{i}'$即可

（之前不能这么做是因为操作有上限，而现在$a_{i}'$已经规定了上限，次数上限无意义）

考虑当处理完$a_{i-1}$和$a_{i}$的免费操作后即可贪心：执行$\min(a_{i-1},a_{i})$次$C_{i-1}$操作和$\max(a_{i-1}-a_{i},0)$次$I_{i-1}$操作

（还有一个细节问题：如果$a+b>a_{i}$，这$a_{i}'$次操作实际上是免费的，因此优先，所以此时$a_{i-1}$只能使用$I_{i-1}$的操作）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int t,n,s1,s2,s3,a[100005];

 4 long long ans;

 5 void calc1(int k,int x){

 6     a[k]-=x;

 7     a[k+1]-=x;

 8     s1+=x;

 9 }

10 void calc2(int k,int x){

11     a[k]-=x;

12     s3+=x;

13 }

14 int main(){

15     scanf("%d",&t);

16     while (t--){

17         scanf("%d",&n);

18         for(int i=1;i<=n;i++)scanf("%d",&a[i]);

19         s1=s2=s3=ans=0;

20         for(int i=1;i<=n;i++){

21             s1=min(s1,a[i]);

22             s2=min(s2,a[i]);

23             int k=max(s1+s2-a[i],0);

24             s1-=k;

25             s2-=k;

26             ans-=k;

27             a[i]-=s1+s2+k;

28             ans+=a[i-1];

29             calc1(i-1,min(a[i-1],a[i]));

30             calc2(i-1,max(a[i-1]-a[i],0));

31             swap(s2,s3);

32             a[i]+=k;

33         }

34         printf("%lld\n",ans+a[n]);

35     }

36 }

巴特西

[loj3313]序列

最新文章

热门文章