1.
//1.完美排列 bool judge(vector<int>&perfect_waiguan,vector<int>&perfect_price,vector<int>&waiguan,vector<int>&price,int K,int begin) { for(int i=0;i<K;i++) { int index=begin+i; if(perfect_waiguan[i]!=waiguan[index] || perfect_price[i]!=price[index] ) return false; } return true; } int main() { int K; cin>>K; vector<int>perfect_waiguan(K,0); vector<int>perfect_price(K,0); for(int i=0;i<K;i++) cin>>perfect_waiguan[i]; for(int i=0;i<K;i++) cin>>perfect_price[i]; int N; cin>>N; vector<int>waiguan(N,0); vector<int>price(N,0); for(int i=0;i<N;i++) cin>>waiguan[i]; for(int i=0;i<N;i++) cin>>price[i]; //遍歷完美排列 6-3=3 int index=0; for(int begin=0;begin<=N-K;begin++) { if(judge(perfect_waiguan,perfect_price,waiguan,price,K,begin))//是完美排列 { index=begin+1; break; } } cout<<index<<endl; }2.
#include <iostream> #include <bits/stdc++.h> using namespace std; //2.DAG int main() { int h,w; cin>>h>>w; vector< vector<int> >M(h,vector<int>(w,0)); for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin>>M[i][j]; //DAG int p_n=w*h; vector< vector<int> >g(p_n,vector<int>(p_n,0)); int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; //建圖 for(int i=0;i<h;i++) for(int j=0;j<w;j++) { int index=w*i+j; for(int k=0;k<4;k++) { int x_new=i+dir[k][0]; int y_new=j+dir[k][1]; int index_new=x_new*w+y_new; // if(x_new<h && x_new>=0 && y_new>=0 && y_new<w && M[i][j]>M[x_new][y_new] ) g[index][index_new]=1; } } //開始拓撲排序 vector<int>dp(p_n,0); vector<int>in(p_n,0); vector<int>visited(p_n,0); for(int j=0;j<p_n;j++) for(int i=0;i<p_n;i++) in[j]=in[j]+g[i][j]; queue<int>q; //in=0 push for(int i=0;i<p_n;i++) if(in[i]==0) { q.push(i); dp[i]=1; } int MAX=0; while(!q.empty()) { int temp=q.front(); //visit visited[temp]=1; MAX=max(MAX,dp[temp]); q.pop(); for(int i=0;i<p_n;i++) { if(g[temp][i]==1 && visited[i]==0) { //dp dp[i]=max(dp[i],dp[temp]+1); in[i]--; if(in[i]==0) q.push(i); } } } cout<<MAX<<endl; }
全部评论
(1) 回帖