#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
int N[]={10,20,30,40,50,50,50,50,50,50};
char infile[100];
char outfile[100];
char cmd[100];
int random(int l,int r)//产生一个范围[l,r]的数
{
return (LL)rand()*rand()*rand()%(r-l+1)+l;
//rand()是系统函数，只能产生[0,32767]的数
//rand()*rand()==1,073,676,289
}
int main()
{
srand(time(0));
for(int t=0;t<10;t++)
{
sprintf(infile,"a%d.in",t);
sprintf(outfile,"a%d.out",t);
freopen(infile,"w",stdout);
int n=N[t];
int m=random(1,n);
printf("%d %d\n",n,m);
fclose(stdout);
sprintf(cmd,"std.exe < %s > %s",infile,outfile);
system(cmd);fprintf(stderr,"正在制造第 %d 组数据\n",t);
}
return 0;
}
有了标程要制造数据的情况，程序如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
int N[]={5,10,100,1000,10000};
char infile[100];
char outfile[100];
char cmd[100];
int main()
{
srand(time(0));
for(int t=0;t<5;t++)
{
sprintf(infile,"a%d.in",t);
sprintf(outfile,"a%d.out",t);
freopen(infile,"w",stdout);
int n=N[t];
printf("%d\n",n);
for(int i=1;i<=n;++i)
{
printf("%llu\n", (LL)rand()*rand()*rand()*rand());
}
fclose(stdout);
fprintf(stderr,"正在制造第 %d 组数据\n",t);
sprintf(cmd,"std.exe < %s > %s",infile,outfile);
system(cmd);
}
return 0;
}
对拍程序《check.cpp》：
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int main(){
int T=0;
while(1){
system("data.exe > 文件名.in");
int t1=clock();
system("vio.exe < 文件名.in > 文件名.ans");
t1=clock()-t1;
int t2=clock();
system("文件名.exe < 文件名.in > 文件名.out");
t2=clock()-t2;
if(system("fc 文件名.ans 文件名.out"))return puts("WA"),0;
printf("#%d: AC, %dms, %dms\n",++T,t1,t2);
Sleep(500);
}
return 0;
}
数据制造程序《data.cpp》：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int N[]={5,50,100,1000,10000,50000,100000,200000,300000,300000};
int M[]={10,50, 20,100,100,500,500,100,200,500};
int random(int l,int r)//产生一个范围[l,r]的数
{
return (LL)rand()*rand()%(r-l+1)+l;
//rand()是系统函数，只能产生[0,32767]的数
//rand()*rand()==1,073,676,289
}
int main()
{
srand(time(0));
int t=0;
int n=N[t],s=rand()%3;
printf("%d %d\n",n,s);
for(int i=1;i<=n;++i)
{
printf("%d %d\n",random(1,20),random(1,20));
}
return 0;
}
暴力朴素程序《vio.cpp》：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=310000;
LL dp[N],f[N],t[N],st[N],sf[N];
int main()
{
//freopen("文件名.in","r",stdin);freopen("文件名.ans","w",stdout);
int n,s;scanf("%d%d",&n,&s);
st[0]=0;sf[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&t[i],&f[i]);
st[i]=st[i-1]+t[i];
sf[i]=sf[i-1]+f[i];
}
memset(dp,63,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>=0;j--)
{
dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
}
}
printf("%lld\n",dp[n]);
return 0;
}
自己打的“正解”（需要不断完善的解）《文件名.cpp》：
/*
dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
dp[i]=dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
dp[i]-st[i]*sf[i]-s*sf[n]= dp[j]-s*sf[j]- st[i]*sf[j]
dp[j]-s*sf[j] =st[i]*sf[j] + dp[i]-st[i]*sf[i]-s*sf[n]
yj=dp[j]-s*sf[j]
xj=sf[j]
k=st[i]
b=dp[i]-st[i]*sf[i]-s*sf[n]
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=310000;
LL dp[N],f[N],t[N],st[N],sf[N],s;int q[N];
double X(int j){ return 1.0*sf[j];}
double Y(int j){ return 1.0*(dp[j]-s*sf[j]);}
double K(int j1,int j2){return ( Y(j1)-Y(j2) ) / ((X(j1)==X(j2))?1e-9: (X(j1)-X(j2)) ) ;}//这里故意出错
int main()
{
//freopen("文件名.in","r",stdin);freopen("文件名.out","w",stdout);
int n;scanf("%d%lld",&n,&s);
st[0]=0;sf[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&t[i],&f[i]);
st[i]=st[i-1]+t[i];
sf[i]=sf[i-1]+f[i];
}
int l=1,r=1;q[1]=0;dp[0]=0;
for(int i=1;i<=n;i++)
{
while(l<r && K(q[l],q[l+1])<=st[i] ) l++;
dp[i]=dp[q[l]]+st[i]*(sf[i]-sf[q[l]])+s*(sf[n]-sf[q[l]]);
while( l<r && K(q[r-1],q[r] ) >= K(q[r],i) ) r--;
q[++r]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
生成多个数据:
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int main(){
for(int t=1;t<=10;t++){
string s;int x=t;
for(;x;x/=10)s+=x%10^48;
reverse(s.begin(),s.end());
system(("maker.exe > "+s+".in").c_str());
system(("std.exe < "+s+".in > "+s+".out").c_str());
Sleep(1000);
}
return 0;
}