比赛概况：100+70+95
貌似老师评测机没插电导致跑慢了，挂35分
T1：水
#include<bits/stdc++.h>
using namespace std;
const int M=10000;
int n,k,a[105][105],dp[105][105][11],ls[1005],top;
int cmp(long long aa,long long bb)
{
return aa>bb;
}
int main()
{
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int h=1;h<=10;h++)
{
dp[i][j][h]=-114514;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
scanf("%lld",&a[i][j]);
}
}
dp[1][1][1]=a[1][1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
top=0;
if(i!=j)
{
for(int h=1;h<=10;h++)
{
if(dp[i-1][j][h]!=-114514)
{
top++;
ls[top]=dp[i-1][j][h];
}
}
}
if(j!=1)
{
for(int h=1;h<=10;h++)
{
if(dp[i-1][j-1][h]!=-114514)
{
top++;
ls[top]=dp[i-1][j-1][h];
}
}
}
if(top!=0)
{
sort(ls+1,ls+top+1,cmp);
for(int h=1;h<=min(top,10);h++)
{
dp[i][j][h]=ls[h]+a[i][j];
// cout<<i<<" "<<j<<" "<<dp[i][j][h]<<endl;
}
}
}
}
top=0;
for(int i=1;i<=n;i++)
{
for(int h=1;h<=10;h++)
{
if(dp[n][i][h]!=-114514)
{
top++;
ls[top]=dp[n][i][h];
}
}
}
sort(ls+1,ls+top+1,cmp);
cout<<ls[k];
return 0;
}
T2：也水
#include<bits/stdc++.h>
using namespace std;
long long n,c[1000005],ls,top,st,last[1000005],head,ans=INT_MAX;
priority_queue<pair<int , int> >q;
struct sd
{
long long sum,id;
}a[2000005];
int cmp(sd A,sd B)
{
return A.sum<B.sum;
}
int main()
{
freopen("eliminate.in","r",stdin);
freopen("eliminate.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&c[i]);
for(int j=1;j<=c[i];j++)
{
scanf("%lld",&ls);
top++;
a[top].sum=ls;
a[top].id=i;
}
}
sort(a+1,a+top+1,cmp);
for(int i=1;i<=top;i++)
{
if(last[a[i].id]==0)
{
last[a[i].id]=i;
st++;
if(st==n)
{
head=i;
break;
}
}
last[a[i].id]=i;
}
for(int i=1;i<=n;i++)
{
q.push(make_pair(-last[i],i));
// cout<<last[i]<<endl;
}
ans=a[head].sum-a[-q.top().first].sum;
//cout<<ans<<endl;
for(int i=head+1;i<=top;i++)
{
last[a[i].id]=i;
q.push(make_pair(-i,a[i].id));
while(-q.top().first<last[q.top().second]) q.pop();
ans=min(ans,a[i].sum-a[-q.top().first].sum);
}
cout<<ans;
return 0;
}
T3：有点难想，但可以发现dp过程中有很多信息可以复用，每次只需要额外判5个（题解3个，应该一样）就好了
#include<bits/stdc++.h>
using namespace std;
long long n,m,p[2005][2005],sum[2005][2005],toh[2005][2005],tol[2005][2005],len,ans,num[2005][2005],lslen;
int main()
{
freopen("rainbow.in","r",stdin);
freopen("rainbow.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&p[i][j]);
if(p[i-1][j-1]==p[i][j])
{
sum[i][j]=sum[i-1][j-1]+1;
}
else sum[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1||j==1) tol[i][j]=1;
else
{
if(p[i][j]==p[i-1][j-1])
{
if(tol[i][j]!=-1) tol[i][j]=tol[i-1][j];
else tol[i][j]=i;
}
else tol[i][j]=-1;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1||j==1) toh[i][j]=1;
else
{
if(p[i][j]==p[i-1][j-1])
{
if(toh[i][j-1]!=-1) toh[i][j]=toh[i][j-1];
else toh[i][j]=j;
}
else
{
toh[i][j]=-1;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((p[i][j]!=p[i-1][j-1])||i==1||j==1)
{
num[i][j]=1;
continue;
}
else
{
len=num[i-1][j-1];
if(len==1)
{
if(p[i-1][j]!=p[i][j-1])
{
num[i][j]=2;
}
else num[i][j]=1;
}
else
{
if(p[i-1][j]!=p[i][j-1])
{
lslen=min(num[i-1][j-1],min(num[i-1][j],num[i][j-1]))+1;
if(p[i][j-lslen+1]!=p[i-lslen+1][j]&&p[i][j-lslen+1]!=p[i-lslen+2][j]&&p[i-lslen+1][j]!=p[i][j-lslen+1]&&p[i-lslen+1][j]!=p[i][j-lslen+2])
{
num[i][j]=lslen;
}
else num[i][j]=lslen-1;
}
else num[i][j]=1;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
// cout<<num[i][j]<<" ";
ans+=num[i][j];
}
// cout<<endl;
}
cout<<ans;
return 0;
}
T4：
老师原话：（只需要dfs就行了）
实际：std代码273行
### 不想改了