最后四个点WA了,一直都WA的最后四个点
附上代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
using namespace std;
int n,t[21],t1[21],a[21],ai[21],b[21],bi[21],used[21],a1,b1,j;
long long ans=0x7fffffff,mi=0x7fffffff;
long long check(){
long long suma=0,sumb=0;
for(int i=1;i<=n;i++){
used[i]=0;
t[i]=t1[i];
a[i]=ai[i];
b[i]=bi[i];
if(t[i]==3){
t[i]=rand()%2+1;
}
}
for(int i=1;i<=n*2;i++){
j=(i-1)%n+1;
if(t[j]==1){
if(used[j]>suma){
suma=used[j]+a[j];
}
else{
suma+=a[j];
used[j]=suma;
t[j]=3-t[j];
}
}
else{
if(used[j]>sumb){
sumb=used[j]+b[j];
}
else{
sumb+=b[j];
used[j]=sumb;
t[j]=3-t[j];
}
}
}
return max(suma,sumb);
}
void sa(){
double T=20000,down=0.99101;
while(T>1e-3){
a1=rand()%n+1;
b1=rand()%n+1;
swap(a[a1],a[b1]);
swap(b[a1],b[b1]);
swap(t[a1],t[b1]);
long long k=check();
if(mi>k){
mi=k;
}
else if(exp(-1*(mi-k)/T)<double(rand())/RAND_MAX);
else{
swap(a[a1],a[b1]);
swap(b[a1],b[b1]);
swap(t[a1],t[b1]);
}
T*=down;
}
}
void solve(){
for(int i=1;i<=400;i++)
sa();
}
int main(){
// freopen("job.in","r",stdin);
// freopen("job.out","w",stdout);
srand(time(0));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t1[i],&ai[i],&bi[i]);
}
solve();
printf("%lld",mi);
return 0;
}