涨了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
西月弦 阅读(328)
评论(1) 编辑 收藏 引用 所属分类:
比赛感言