Untitled
unknown
plain_text
2 years ago
1.0 kB
5
Indexable
#include <iostream> #define N 1001 #define oo 2000000 using namespace std; int n,m; int x[N]; int a[N],b[N]; int ans; int linh[N*N]; int cong; void doc() { cin>>n; ans=oo; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; } cong=0; } void backtrack(int u, int cp, int ar0, int ar1, int ar2) { if(u==n+1) { //for(int i=1;i<=n;i++)cout<<x[i]<<" "; //cout<<"\n"<<cp<<"\n"; if(cp<ans)ans=cp; return; } x[u]=0; if(cp+b[u]<ans)backtrack(u+1,cp+b[u],ar0,ar1,ar2); x[u]=1; if(cp+2*b[u]<ans)backtrack(u+1,cp+b[u]*2,ar0+a[u],ar1,ar2); if(ar0+ar1+ar2>=a[u]) { int linh=a[u]; linh-=ar2; if(linh<0)linh=0; int i,j,l; i=0; j=ar0; l=ar1; if(linh>l) { linh-=l; l=0; j-=linh; linh=0; }else l-=linh,linh=0; backtrack(u+1,cp,i,j,l); cong--; } } int main() { //freopen("input.txt","r",stdin); int TC; cin>>TC; for(int tc=1;tc<=TC;tc++) { doc(); backtrack(1,0,0,0,0); cout<<"#"<<tc<<" "<<ans<<"\n"; } return 0; }
Editor is loading...