E. Arena 2100
https://codeforces.com/problemset/problem/1606/E
题意见洛谷。
n,x<=500
题解：显然是一道dp，考虑状态：需要能够随转移变化的状态，而转移显然是生命值的变化和人数的变化，什么生命值最能表征当前状态？最大生命值。故令f[i][j]表示总人数为i，最大生命值为j时的可行方案数。
当j<=i-1时，显然下一步全死，故f[i][j]=ji-(j-1)i;
ELSE f[i][j]=∑(f[k][j-i+1]C(i,k)(i-1)^(i-k));（注意人是不同的）
代码：
#define int long long
using namespace std;
const int N=605,mod=998244353;
int f[N][N],fac[N],finv[N],c[605][605];
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=505;i++){
fac[i]=fac[i-1]*i%mod;
}
for(int i=0;i<=505;i++){
finv[i]=qpow(fac[i],mod-2);
}
}
int mo(int x){
x=x%mod;
if(x<0) x+=mod;
if(x>mod) x-=mod;
return x;
}
int C(int n,int m){
if(m==0) return 1;
return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
signed main(){
int n,x;cin>>n>>x;
init();
for(int i=2;i<=n;i++){
for(int j=1;j<=x;j++){
if(j<=i-1) f[i][j]=((qpow(j,i)-qpow(j-1,i))%mod+mod)%mod;
else{
int& w=f[i][j];
for(int k=1;k<=i;k++){
w=(w+C(i,k)*f[k][j-i+1]%mod*qpow(i-1,i-k)%mod)%mod;
}
}
}
}
int ans=0;
for(int i=1;i<=x;i++){
ans=(ans+f[n][i])%mod;
}
cout<<ans;
}
New Game Plus! 2200
https://www.luogu.com.cn/problem/CF1415E
题解：观察一波，好像一个dp，一看数据，好像不太行，考虑贪心，而根据数据猜测是一个nlogn解法，可能是用堆。
正经分析开始：其给的k个归零操作实质上是把其分为k+1个组，贪心地，每个组元素不增。当放入一个元素时，获取该组当前地值f[i],f[i]->f[i]+a[k],易知用最大的那一组是最优的，故将组放入堆中，每次取top即可。
代码：
#define int long long
using namespace std;
const int N=5e5+100,INF=1e18;
int n,k;
int a[N],b[N],c[N],cnt[N];
priority_queue<int> q;
signed main(){
cin>>n>>k;
int w=n+1,tot=0,ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) b[i]=a[n-i+1];
for(int i=1;i<=k+1;i++) q.push(0);
for(int i=1;i<=n;i++){
int x=q.top();q.pop();
ans+=x;
q.push(x+b[i]);
}
cout<<ans;
}