算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
涨了47 rating,不错~

A题

大概就是给你两个长度为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 

B题

有个大小为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 西月弦 阅读(336) 评论(1)  编辑 收藏 引用 所属分类: 比赛感言

FeedBack:
# re: codeforces #119 div1
2012-05-12 18:55 | Lupus_primer
orz!!!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理