最优时间表问题.txt

来自「算法设计与分析源代码算法设计与分析源代码」· 文本 代码 · 共 64 行

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
void main() 
{ 
int way[31][31]; 
vector<int> w[31]; 
int length,s,begin,last,i,j,k,f; 
cin>>length>>s; 
for(i=1;i<=s;i++) 
{ 
cin>>begin>>last; 
w[begin].push_back(last); 
 sort(w[begin].begin(),w[begin].end()); 
} 
for(i=1;i<=length;i++) 
{ 
for(j=i;j<=length;j++) 
{ 
way[i][j]=-2; 
} 
if(w[i].size()&&w[i][0]==1) 
way[i][i]=1; 
else if(w[i].size()==0) 
way[i][i]=0; 
if(w[i].size()&&w[i][0]>1) 
for(j=i;j<i+w[i][0]-1;j++) 
way[i][j]=-1; 
} 
for(i=2;i<=length;i++) 
{ 
for(j=1;j<=length-i+1;j++) 
{ if(way[j][j+i-1]==-1) 
 continue; 
 for(k=j;k<=j+i-2;k++) 
 { 
 if(way[j][k]==-1||way[k+1][j+i-1]==-1) 
 continue; 
 else 
 { 
 if(way[j][j+i-1]==-2) 
 way[j][j+i-1]=way[j][k]+way[k+1][j+i-1]; 
 else 
 { 
 if(way[j][k]+way[k+1][j+i-1]<way[j][j+i-1]) 
 way[j][j+i-1]=way[j][k]+way[k+1][j+i-1]; 
 } 
 } 
 } 
 if(way[j][j+i-1]==-2) 
 { 
 for(f=0;f<w[j].size();f++) 
 if(w[j][f]==i) 
 break; 
 if(f==w[j].size()) 
 way[j][j+i-1]=-1; 
 else 
 way[j][j+i-1]=i; 
 } 
} 
} 
cout<<way[1][length]<<endl; 
}