题目概述

$$ f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{f(x-1,y-1),f(x-1),y\}+A_y&\text{otherwise}\end{cases} $$

$q$ 组询问求 $f(x,y)$ 。

解题报告

可能不难吧……但是我不会做……

先找一些显然的性质简化问题：最优策略肯定是先往左上角走到一个比较小的 $A_y$ 然后走到头。正确性的话考虑把所有往左上角走的合并，那么不可能中间又往左上角走，这明显不优。

然后就可以写出式子：$f(x,y)=min\{sum_A[y]-sum_A[i]+(x-y+i)A_i|i\le y\}$ ，发现长得像斜率优化。

因为有 $i\le y$ 这个限制，而且多组询问，所以必须离线才能做。但 $A_i$ 不递增？不过很明显 $A_i>A_j\land i<j$ 的 $i$ 是没有用的，于是只要保证维护斜率的栈是 $A$ 单调的。然后就是 $x-y$ 不确定，那么得二分找最优点。

但我们还会发现一个问题：如果 $x-y+i<0$ 好像咕咕咕了？由于 $A$ 单调所以这种状态肯定不优，二分答案的时候不会被选中，所以没关系。

排除了这么多种特殊情况之后就可以愉快的写啦。

示例程序

这道题还不明觉厉的爆long long，乘的时候套了个long double就玄学的过了。

#include<cstdio>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=500000,maxq=500000;

int n,Q,a[maxn+5];LL sum[maxn+5],f[maxn+5],ans[maxq+5];
int top,stk[maxn+5];vector< pair<int,int> > q[maxn+5];

#define X(i,j) (a[j]-a[i])
#define Y(i,j) (f[j]-f[i])
inline LL getans(int i,int x,int y) {return sum[y]-sum[stk[i]]+(LL)(x-y+stk[i])*a[stk[i]];}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i],f[i]=sum[i]-(LL)i*a[i];
    scanf("%d",&Q);for (int i=1,x,y;i<=Q;i++) scanf("%d%d",&x,&y),q[y].push_back(mp(x,i));
    for (int i=1;i<=n;i++){
        while (top&&a[stk[top]]>a[i]) top--;
        while (top>1&&(DB)Y(stk[top-1],stk[top])*X(stk[top],i)<=(DB)Y(stk[top],i)*X(stk[top-1],stk[top])) top--;stk[++top]=i;
        for (int j=0,si=q[i].size(),x;j<si;j++){
            x=q[i][j].fr;int L=1,R=top-1;
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                getans(mid,x,i)<=getans(mid+1,x,i)?R=mid-1:L=mid+1;
            ans[q[i][j].sc]=getans(L,x,i);
        }
    }
    for (int i=1;i<=Q;i++) printf("%lld\n",ans[i]);return 0;
}