想法:b=x⋅t+y⋅t′。
枚举,O(qn3),加了俩优化就过了并且 76 ms。
#include<bits/stdc++.h>
using namespace std;
int b[2005],c[2005],t[2005],n;
int pd(int x,int y){
for(int i=1;i<=n;i++){
if(x*b[i]+y*c[i]>t[i]) return -1;
if(x*b[i]+y*c[i]<t[i]) return 0;
}
return 1;
}
int read(){
int x=0,f=1;char c=getchar();
while(c<48||c>57){if(c=='-') f=-1;c=getchar();}
while(c>47&&c<58) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
int main(){
int T;
cin>>T;
while(T--){
memset(c,0,sizeof(c));
n=read();
int mx=0;
for(int i=1;i<=n;i++)
b[i]=read(),c[i]+=b[i],c[n-i+1]+=b[i];
for(int i=1;i<=n;i++)
t[i]=read(),mx=max(mx,t[i]);
bool flag=0;
for(int i=0;i<=mx;i++){
for(int j=0;j<=mx;j++){
int kkk=pd(i,j);
if(kkk==-1) break;
if(kkk){
flag=1;
break;
}
}
if(flag) break;
}
if(flag==1) cout<<"yes\n";
else cout<<"no\n";
}
return 0;
}