漲了47 rating,不錯(cuò)~大概就是給你兩個(gè)長(zhǎng)度為N(N<20,000)的1-N的排列，你每次可以將第一個(gè)數(shù)列的最后一個(gè)元素插入到前面的某個(gè)位置。
請(qǐng)問(wèn)最少進(jìn)行多少次操作能將數(shù)列1變?yōu)閿?shù)列2
分析：
如果把數(shù)列2置換成1,2,...,n的話，數(shù)列1也有一個(gè)排列a0,a1,...,an-1。
數(shù)列{a}前面有多少個(gè)第增的元素，我們就要將最后一個(gè)遞增的元素的后面的所有元素插入到前面。
17min 1A
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 using namespace std;
6 #define re(i,n) for(int i=0;i<n;i++)
7 #define re1(i,n) for(int i=1;i<=n;i++)
8 #define re2(i,n) for(int i=0;i<=n;i++)
9 #define re3(i,n) for(int i=1;i<n;i++)
10 #define clr(a,n) memset(a,n,sizeof(a))
11 #define debug(n) cout<<#n<<"="<<n<<endl
12 const int N = 1000000;
13 struct node {
14 int val,id;
15 } num[N];
16 int temp[N],hash[N];
17 int main(){
18 int n;
19 while(cin >>n){
20 clr(hash,0);
21 re(i,n) {
22 cin >> num[i].id;
23 hash[num[i].id] = i;
24 }
25 re(i,n) cin >> temp[i];
26 re(i,n) num[hash[temp[i]]].val = i;
27 int ans = 1;
28 re3(i,n) if(num[i].val < num[i-1].val) break;
29 else ans ++;
30 cout<<n-ans<<endl;
31 }
32 }
33
有個(gè)大小為N(N<60)的完全圖和M(M<60)的賽車(chē)。已知每個(gè)賽車(chē)k在每個(gè)邊(i,j)上的運(yùn)行時(shí)間為f[k,i,j]。
詢問(wèn)R(R<10,000)次，每次詢問(wèn)從si出發(fā)到ti且最多換車(chē)ki(ki<1,000)次的最少時(shí)間是多少？
分析：
先把每個(gè)賽車(chē)在這個(gè)圖上的多源最短路搞出來(lái)f[k,i,j]...
令dp[k,i,j]為從i到j(luò)最多換車(chē)k次的最小時(shí)間。
顯然dp[0,i,j] = min(f[p,i,j]) (for all p that 0<=p<m)
最多換車(chē)n次就可以了 - -
那么dp[k,i,j] = min(dp[k-1,i,p]+dp[0,p,j]) (for all p that belong to G)
中間犯了一個(gè)初始化的NC錯(cuò)誤... 59min 2A
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 using namespace std;
6 #define re(i,n) for(int i=0;i<n;i++)
7 #define re1(i,n) for(int i=1;i<=n;i++)
8 #define re2(i,n) for(int i=0;i<=n;i++)
9 #define re3(i,n) for(int i=1;i<n;i++)
10 #define clr(a,n) memset(a,n,sizeof(a))
11 template <typename T> inline T chkmin(T &a,const T b){ return a > b ? a = b : a ; }
12 template <typename T> inline T chkmax(T &a,const T b){ return a < b ? a = b : a ; }
13 const int V = 65;
14 const int inf = ~0u>>2;
15 int G[V][V][V],dp[V][V][V],num[V][V];
16 int main(){
17 int n,m,r;
18 while(~scanf("%d%d%d",&n,&m,&r)){
19 re(p,m){
20 re(i,n) re(j,n) scanf("%d",&G[p][i][j]);
21 re(k,n) re(i,n) re(j,n) chkmin(G[p][i][j],G[p][i][k]+G[p][k][j]);
22 }
23 re2(i,n) re(j,n) re(p,n) dp[i][j][p] = inf;
24 re(i,n) re(j,n) re(p,m) chkmin(dp[0][i][j],G[p][i][j]);
25 re1(k,n) re(i,n) re(j,n) re(p,n) chkmin(dp[k][i][j] ,dp[k-1][i][p] + dp[0][p][j]);
26 re2(k,n){
27 // re(i,n) {re(j,n) cout<<dp[k][i][j]<<" ";cout<<endl;}
28 }
29 re(i,r){
30 int a,b,c;
31 scanf("%d%d%d",&a,&b,&c);
32 if(c>=n) c = n;
33 printf("%d\n",dp[c][a-1][b-1]);
34 }
35 }
36 }
37
posted on 2012-05-11 06:48
西月弦 閱讀(353)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
比賽感言