题意:洛谷翻译超可爱的放一下qwq
解:先设dp[i][j]为安排前 i 个人接前 j 只猫的最小等待时间。显然要给猫排个序。猫可以等人,但人不会等猫。于是算一下每只猫需要人在什么时候出发,刚好能接到,这样就保证了人能接到连续一段猫猫。我们称这个时间为猫猫时间(dbq猫猫真的太可爱了)。如果要接[k, j]的猫,只能按照第 j 只猫的猫猫时间出发,不然接不到前面的猫,于是这一段猫猫的等待时间为(j-k+1)*h[j]-sum[k...j]。按这个推一下式子,转移即可。
顺带一提如果人类的数量大于猫猫,那可以安排每个人接一只猫,总时间为0.
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define maxx 100005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 2520 ll dp[105][maxx]={0}; ll sum[maxx]={0}; ll d[maxx],h[maxx],t[maxx]; int q[maxx]={0}; double cal(int m,int n,int i){ return ((double)dp[i-1][m]-dp[i-1][n]+sum[m]-sum[n])/(m-n); } signed main() { int n,m,p; scanf("%d%d%d",&n,&m,&p); for(int i=2;i<=n;i++){ scanf("%lld",&d[i]); } for(int i=1;i<=n;i++){ d[i]=d[i]+d[i-1]; } for(int i=1;i<=m;i++){ scanf("%lld%lld",&h[i],&t[i]); } if(p>=m){ printf("0\n"); return 0; } for(int i=1;i<=m;i++){ t[i]=t[i]-d[h[i]]; } sort(t+1,t+m+1); for(int i=1;i<=m;i++){ sum[i]=sum[i-1]+t[i]; } dp[1][0]=0; for(int i=1;i<=m;i++){ dp[1][i]=i*t[i]-sum[i]; } for(int i=2;i<=p;i++){ int head=1,tail=1; q[head]=0; for(int j=1;j<=m;j++){ while(head<tail&&cal(q[head],q[head+1],i)<t[j]) head++; int k=q[head]; dp[i][j]=dp[i-1][k]+(j-k)*t[j]-sum[j]+sum[k]; while(head<tail&&cal(q[tail-1],q[tail],i)>=cal(q[tail],j,i)) tail--; q[++tail]=j; } } printf("%lld\n",dp[p][m]); } // a[i]=t[i]-h[i] // dp[i][j] use i feeder to take the first j cats // dp[i][j]=min(dp[i-1][k]+val(k+1,j)) // val(k+1,j)=num*a[j]-sum[k+1...j]=(j-k)*a[j]-sum[j]+sum[k] // dp[i][j]=min(dp[i-1][k]+(j-k)*a[j]-sum[j]+sum[k]) // dp[i][j]=min(dp[i-1][k]+j*a[j]-sum[j]+sum[k]-k*a[j]) // if m is better than n // dp[i-1][m]+sum[m]-m*a[j]<dp[i-1][n]+sum[n]-n*a[j] // (dp[i-1][m]-dp[i-1][n]+sum[m]-sum[n])/(m-n)<a[j]View Code
顺便发点今日份猫fei猫mi
标签:maxx,int,sum,CodeForces,猫猫,Cats,Transport,dp,define From: https://www.cnblogs.com/capterlliar/p/16921940.html