AW303 运输小猫

本文主要是介绍AW303 运输小猫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

易错点：

• 笔者由于没有进行数据初始化（排序以及数据填充）和状态转移中的一个字母r写成了l而调试了近一个小时.

---

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=1e5+10,MAXP=110;
ll f[MAXP][MAXN],sumD[MAXN];
ll A[MAXN],sumA[MAXN];
int q[MAXN],l,r;
int main(){int n,m,p;scanf("%d%d%d",&n,&m,&p);for(int i=2;i<=n;i++){int d;scanf("%d",&d);sumD[i]=sumD[i-1]+d;}for(int i=1;i<=m;i++){int h,t;scanf("%d%d",&h,&t);A[i]=t-sumD[h];}sort(A+1,A+m+1);for(int i=1;i<=m;i++)sumA[i]=sumA[i-1]+A[i];memset(f,0x3f,sizeof(f));f[0][0]=0;for(int i=1;i<=p;i++){q[l=r=1]=0;for(int j=1;j<=m;j++){ll nowK=A[j];while(l<r&&f[i-1][q[l+1]]+sumA[q[l+1]]-f[i-1][q[l]]-sumA[q[l]]<nowK*(q[l+1]-q[l]))l++;f[i][j]=f[i-1][q[l]]+sumA[q[l]]-q[l]*A[j]+j*A[j]-sumA[j];while(l<r&&(f[i-1][q[r]]+sumA[q[r]]-f[i-1][q[r-1]]-sumA[q[r-1]])*(j-q[r])>(f[i-1][j]+sumA[j]-f[i-1][q[r]]-sumA[q[r]])*(q[r]-q[r-1]))r--;q[++r]=j;}}printf("%lld\n",f[p][m]);return 0;
}

 

这篇关于AW303 运输小猫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---