1026.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main(){
  //ifstream cin("1026.txt");
  int casenum,i,j,k,l;
  cin>>casenum;
  for(l=0;l<casenum;l++){
     cin>>k; vector<int> a(k);
	 for(i=0;i<k;i++) cin>>a[i];
     cin>>k; vector<int> b(k);
	 for(i=0;i<k;i++) cin>>b[i];
     cin>>k; vector<int> c(k);
	 for(i=0;i<k;i++) cin>>c[i];
     vector<int> m(a.size()+b.size()-1,0);
	 for(i=0;i<a.size();i++)
		 for(j=0;j<b.size();j++)
			 m[i+j]+=a[i]*b[j];
     for(i=0;i<m.size();i++){
		 m[i]%=2;
	 }
	 //注意！！m.size()-c.size()是unsigned！！！
	 int tt=m.size();
	 tt-=c.size();
     for(i=0;i<=tt/*i<m.size()-c.size()*/;i++){
         if(m[i]==1){
             for(j=0;j<c.size();j++){
                if(m[i+j]==1&&c[j]==0||m[i+j]==0&&c[j]==1) m[i+j]=1;
				else m[i+j]=0;
			 }
		 }
	 }
	 while(m[0]==0) m.erase(&m[0]);
	 cout<<m.size();
     for(i=0;i<m.size();i++){
		 cout<<" "<<m[i];
	 }
	 cout<<endl;
  }
}