30+0+10+0
全真模拟。今天的模拟赛有一种格外的说不上来的绝望的感觉。很不好描述的。一直在想如果这是真实的 noip 赛场那我不就大寄特寄了。
下午因为不舒服所以玩了一下午（？）一直在机惨别人（？）玩的很开心。
但还是想看大家在机房跳钢管舞喵（？
赛时看到这个题之后就变得很愚蠢。写了奇怪的桶 + 暴力背包，调了两个小时，最后获得了 30pts 的好成绩。是谁破防了我不说。
正解是，背包。倒着这样跑回跳过许多无用的数。在洛谷上可以跑过，oj 的机子需要火车头或者数组随机排序。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const int M=1e3+10;
int n,m;
int s1,s2;
int vis1[N],vis2[N];
ll w1[M],v1[M],w2[M],v2[M];
ll f[N],g[N];
ll ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&w1[i],&v1[i]);
s1+=w1[i];
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",&w2[i],&v2[i]);
s2+=w2[i];
}
memset(f,-0x3f,sizeof f);
memset(g,-0x3f,sizeof g);
vis1[0]=1,vis2[0]=1;
g[0]=f[0]=0;
for(int i=1;i<=n;i++)
for(int j=s1;j>=w1[i];j--)
if(vis1[j-w1[i]]){
f[j]=max(f[j],f[j-w1[i]]+v1[i]);
vis1[j]=1;
}
for(int i=1;i<=m;i++)
for(int j=s2;j>=w2[i];j--)
if(vis2[j-w2[i]]){
g[j]=max(g[j],g[j-w2[i]]+v2[i]);
vis2[j]=1;
}
for(int i=1;i<=min(s1,s2);i++)
if(vis1[i]&&vis2[i]) ans=max(ans,f[i]+g[i]);
printf("%lld",ans);
}
这是 20pts 的暴力凑点字数。赛时最后 2h 大脑再次宕机无法思考，没考虑到序列有负数嗯...
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52;
int T;
int n;
int a[N][N];
void solve(){
int k;
scanf("%lld%lld",&n,&k);
int s1=0,s2=0;
int ans1=0,ans2=0;
a[1][1]=0;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%lld",&a[i][j]);
}
s1+=a[i][1];
s2+=a[i][i];
ans1=max(ans1,s1);
ans2=max(ans2,s2);
}
printf("%lld\n",ans1+ans2);
}
signed main(){
scanf("%lld",&T);
while(T--) solve();
}
C 大模拟。
D 不会