漲了47 rating,不錯~大概就是給你兩個長度為N(N<20,000)的1-N的排列，你每次可以將第一個數列的最后一個元素插入到前面的某個位置。
請問最少進行多少次操作能將數列1變為數列2
分析：
如果把數列2置換成1,2,...,n的話，數列1也有一個排列a0,a1,...,an-1。
數列{a}前面有多少個第增的元素，我們就要將最后一個遞增的元素的后面的所有元素插入到前面。
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
有個大小為N(N<60)的完全圖和M(M<60)的賽車。已知每個賽車k在每個邊(i,j)上的運行時間為f[k,i,j]。
詢問R(R<10,000)次，每次詢問從si出發到ti且最多換車ki(ki<1,000)次的最少時間是多少？
分析：
先把每個賽車在這個圖上的多源最短路搞出來f[k,i,j]...
令dp[k,i,j]為從i到j最多換車k次的最小時間。
顯然dp[0,i,j] = min(f[p,i,j]) (for all p that 0<=p<m)
最多換車n次就可以了 - -
那么dp[k,i,j] = min(dp[k-1,i,p]+dp[0,p,j]) (for all p that belong to G)
中間犯了一個初始化的NC錯誤... 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
西月弦 閱讀(362)
評論(1) 編輯 收藏 引用 所屬分類:
比賽感言