Untitled
unknown
plain_text
a year ago
1.6 kB
4
Indexable
#include <iostream>; using namespace std; int N,MIN; int VT[5],SL[5],V[5],A[70]; int Trai(int cua) { int people = SL[cua]; int vt = VT[cua]; int j=0; int value=0; while (people>0) { if( vt-j >0 && A[vt-j]==0) { A[vt-j] = cua; value+= j+1; people--; } if( vt+j <=N && A[vt+j]==0 && people!=0) { A[vt+j] = cua; value+= j+1; people--; } j++; } return value; } int Phai(int cua) { int people = SL[cua]; int vt = VT[cua]; int j=0; int value=0; while (people>0) { if( vt+j <=N && A[vt+j]==0) { A[vt+j] = cua; value+= j+1; people--; } if( vt-j >0 && A[vt-j]==0 && people!=0) { A[vt-j] = cua; value+= j+1; people--; } j++; } return value; } void BackTrack(int index, int sum) { if(index == 3) { //for(int i=0;i<=N;i++) cout<<A[i]<<" "; //cout<<MIN<<" "<<sum<<endl; if(MIN>sum) { MIN=sum; } return; } for(int i=1;i<=3;i++) { if(V[i]==0) { V[i]=1; BackTrack(index+1,sum+Trai(i)); //V[i]=0; for(int a=0;a<=N;a++) { if(A[a]==i) { A[a]=0; } } BackTrack(index+1, sum+Phai(i)); V[i]=0; for(int a=0;a<=N;a++) { if(A[a]==i) { A[a]=0; } } } } } int main() { freopen("Text.txt","r",stdin); int T; cin>>T; for(int tc=1;tc<=T;tc++) { cin>>N; for(int i=1;i<=3;i++) { cin>>VT[i]>>SL[i]; V[i]=0; } } for(int i=0;i<=N;i++) { A[i]=0; } MIN=9999; BackTrack(0,0); cout<<MIN; return 0; }
Editor is loading...
Leave a Comment