admin 管理员组

文章数量: 1184232

王者荣耀

WZRY

为了排位赛的Cjj神，最近耗尽气力来打WZRY。

Cjj神最近有N局预约的排位赛，其中第i局需要耗时Li的时间。因为浓浓的Gay情，Cjj神不能改变这些排位赛的的顺序。作为一个很有（mei）自制力的人，Cjj神计划用M+1天打完N局，为了能够活着见到第M+2天的太阳，他希望耗时最长的一天最短。

每天最少打一局。

请告诉他这个值是多少，以使他判断他是否能活下来；并且告诉他在总时长最长一天等于这个最小值的情况下有多少种方案，以使他判断他活下来的概率是多少。

输入格式：

第一行两个整数N,M。

接下来N个整数Li。

输出格式：

一行两个数，第一个是总时长最长的一天的最小值，第二个数是方案总数，对10,007取模。

数据范围：

10%：N<=25

30%：N<=300

60%：N<=10000

100%：N<=50000，0<=m< n，m<1000，1<=Li<=1000

这道题有两问，第一问可以很简单地用二分+贪心解决。

但第二问呢？

首先这道题的普通暴力DP是很好想到的，设f[i][j]为第i天，打了j局比赛的方案总数。

很显然f[i][j]=∑f[i-1][k]（sum[j]-sum[k]<=ans）

sum为Li的前缀和。

奉上暴力代码：

#include <bits/stdc++.h>
#define mod 10007
using namespace std;
inline char tc(){static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline int read(){char c;while(!isdigit(c=tc()));int x=c-'0';while(isdigit(c=tc()))x=x*10+c-'0';return x;
}
int n,m,a[30001],mx,ans,ww,f[1001][30001],sum[30001];
int check(int x){int tot=0,last=x,d=1;for(int i=1;i<=n;i++)if(last>=a[i])last-=a[i];else d++,last=x-a[i];return d<=m;
}
int main(){n=read(),m=read();m++;for(int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),ww+=a[i],sum[i]=sum[i-1]+a[i];int L=mx,R=ww;while(L<=R){int mid=L+R>>1;if(check(mid))R=mid-1,ans=mid;else L=mid+1;}//二分，第一问for(int i=1;i<=m;i++){f[i-1][0]=1;for(int j=i;j<=n;j++){for(int k=i-1;k<j;k++)if(sum[j]-sum[k]<=ans)f[i][j]=(f[i][j]+f[i-1][k])%mod;}}int tot=0;for(int i=1;i<=m;i++)tot=(tot+f[i][n])%mod;printf("%d %d",ans,tot);
}

这个O(M*N^2)的效率一定会超时，所以我们要对暴力优化。

仔细看这个暴力，不难发现其实是一个不停枚举j和k边界的过程。

又想到我们知道最大耗时的最小值，那么就可以在已知k便边界的情况下通过预处理求出j边界的值。

设pre[i]表示第i局最远可以由哪一局转移过来。

那么只需枚举k加前缀和维护f数组的值就可以得到O(MN)的算法了。

但通过观察数据可得内存会炸，由于有前缀和维护，只需要每次i做完1次时将f清零即可。

code：

#include <bits/stdc++.h>
#define mod 10007
#define ll long long
using namespace std;
inline char tc(){static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline int read(){char c;while(!isdigit(c=tc()));int x=c-'0';while(isdigit(c=tc()))x=x*10+c-'0';return x;
}
int n,m,a[30001],mx,ans,ww,f[30001];
int sum[30001],pre[30001],d[30001];
int check(int x){int tot=0,last=x,d=1;for(int i=1;i<=n;i++)if(last>=a[i])last-=a[i];else d++,last=x-a[i];return d<=m;
}
int main(){n=read(),m=read();m++;for(int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),ww+=a[i],sum[i]=sum[i-1]+a[i];int L=mx,R=ww;while(L<=R){int mid=L+R>>1;if(check(mid))R=mid-1,ans=mid;else L=mid+1;}for(int i=1;i<=n;i++){int sum=0;for(int j=i;j>0;j--){if(sum+a[j]<=ans)sum+=a[j];else {pre[i]=j;break;}}}//预处理prefor(int i=0;i<=n;i++)d[i]=1;int tot=0;for(int i=1;i<=m;i++){for(int j=i;j<=n;j++){if(pre[j]>0)f[j]=(f[j]+d[j-1]-d[pre[j]-1])%mod;else f[j]=(f[j]+d[j-1])%mod;}d[0]=0;tot=(tot+f[n])%mod;for(int j=1;j<=n;j++)d[j]=(d[j-1]+f[j])%mod,f[j]=0;//维护，清零}tot=((tot+mod)%mod+mod)%mod; printf("%d %d",ans,tot);
}

本文标签： 王者荣耀

版权声明：本文标题：王者荣耀 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687368667a94711.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。