辣鸡wyz最近状态奇差，于是想用usaco题找找手感，万万没想到被虐了一脸TAT
先贴代码，有空再填坑
4409[Usaco2016 Feb]Circular barn
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 2333 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} ll s[N][N];
int n,m,a[N];
ll dp[10][N];
int p[10][N];
int sl[N],sr[N],stk[N],top; int main(){
n=read();m=read();
for (int i=1;i<=n;++i) a[i+n]=a[i]=read();
for (int i=1;i<=n;++i){
s[n+i][0]=s[i][0]=0;
for (int j=1;j<=n;++j)
s[n+i][j]=s[i][j]=s[i][j-1]+(ll)a[i+j-1]*(j-1);
}
top=1;sl[0]=0;sr[0]=n+1;
for (int i=0;i<top;++i){
stk[i]=(sl[i]+sr[i])/2;
if (sl[i]+1<stk[i]){
sl[top]=sl[i];
sr[top]=stk[i];
++top;
}
if (stk[i]+1<sr[i]){
sl[top]=stk[i];
sr[top]=sr[i];
++top;
}
} ll ans=(1LL<<60);
for (int st=1;st<=n;++st){
for (int i=0;i<=n;++i) dp[1][i]=s[st][i],p[1][i]=0;
for (int k=2;k<=m;++k) p[k][n+1]=n,p[k][0]=0,dp[k][0]=0;
for (int k=2;k<=m;++k)
for (int i=0;i<top;++i){
int now=stk[i];
dp[k][now]=(1LL<<60);
for (int j=p[k][sl[i]];j<=p[k][sr[i]]&&j<=now;++j)
if (dp[k][now]>dp[k-1][j]+s[st+j][now-j]){
dp[k][now]=dp[k-1][j]+s[st+j][now-j];
p[k][now]=j;
}
}
ans=min(ans,dp[m][n]);
}
printf("%lld\n",ans);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 25003 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} int n,m,a[N],b[N]; int main(){
a[0]=read();b[0]=read();n=read();m=read();
for (int i=n;i;--i) a[i]=read();
sort(a,a+n+1,greater<int>());
for (int i=0;i<=n;++i) a[i]=a[i]-a[i+1];
sort(a,a+n+1);
for (int i=m;i;--i) b[i]=read();
sort(b,b+m+1,greater<int>());
for (int i=0;i<=m;++i) b[i]=b[i]-b[i+1];
sort(b,b+m+1); int p=1,q=1;
ll ans=(ll)a[0]*m+(ll)b[0]*n;
while (p<=n&&q<=m)
if (a[p]<b[q])
ans+=(ll)a[p++]*(m-q+1);
else
ans+=(ll)b[q++]*(n-p+1);
printf("%lld\n",ans);
return 0;
}
4411[Usaco2016 Feb]Load balancing
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 100005 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} int n;
int c[2][40*N]; void modify(int id,int pos,int delta){
for (int x=1,l=1,r=1e6;;){
c[id][x]+=delta;
if (l==r) break;
int mid=(l+r)/2;
if (pos<=mid) x=(x<<1),r=mid;
else x=(x<<1^1),l=mid+1;
}
} int query(){
int ds[2]={0,0},us[2]={0,0};
for (int x=1,l=1,r=1e6;;){
int ls=x<<1,rs=x<<1^1,mid=(l+r)/2;
if (l==r) ls=rs=x;
if (max(ds[0]+c[0][ls],ds[1]+c[1][ls])<max(us[0]+c[0][rs],us[1]+c[1][rs])){
ds[0]+=c[0][ls];ds[1]+=c[1][ls];x=rs;l=mid+1;
}
else{
us[0]+=c[0][rs];us[1]+=c[1][rs];x=ls;r=mid;
}
if (ls==rs) return max(max(ds[0],ds[1]),max(us[0],us[1]));
}
} struct point{
int x,y;
} a[N];
inline bool operator <(const point &u,const point &v){
return u.x<v.x;
} int main(){
n=read();
memset(c,0,sizeof(c));
for (int i=1;i<=n;modify(1,a[i++].y=read(),1)) a[i].x=read();
sort(a+1,a+n+1);
int ans=query();
for (int i=1;i<=n;++i){
modify(0,a[i].y,1);
modify(1,a[i].y,-1);
if (i<n&&a[i].x==a[i+1].x) continue;
ans=min(ans,query());
}
printf("%d\n",ans);
return 0;
}