牛客 牛牛的猜球游戏动态规划

牛牛的猜球游戏_牛客网

         对于第1~n个操作组合，以及序列的0~9个数字，我们令f[i][j]表示进行完前i次操作后，序列中第j位数字是多少，根据题意模拟对f[i][j]进行初始化

         当我们要求解操作第a次到第b次时，由于我们在f[i][]中记录的是进行了前i次操作的序列，但是无妨！我们将进行了前a-1次的序列数，按顺序映射为0~9，此时f[b][]中为进行了前b次操作的序列，经过映射后我们得到的就是操作第a次到第b次后的序列

1.  
   #include<iostream>
2.  
   #include<cstdio>
3.  
   #include<limits.h>
4.  
   using namespace std;
5.  
   const int N=1e5 5;
6.  
   int f[N][15];//f[i][j]进行完前i个操作后，第j位是哪个数
7.  
   int res[15];
8.  
   int main()
9.  
   {
10.  
    int n,m;cin>>n>>m;
11.  
    for(int i=0;i<10;i ) f[0][i]=i;
12.  
    for(int i=1;i<=n;i )
13.  
    {
14.  
    int a,b;cin>>a>>b;
15.  
    for(int j=0;j<10;j )
16.  
    f[i][j]=f[i-1][j];
17.  
    swap(f[i][a],f[i][b]);
18.  
    }
19.  
    while(m--)
20.  
    {
21.  
    int a,b;cin>>a>>b;
22.  
    for(int i=0;i<10;i ) res[f[a-1][i]]=i;
23.  
    for(int i=0;i<10;i )
24.  
    {
25.  
    cout<<res[f[b][i]];
26.  
    if(i!=9) cout<<" ";
27.  
    else cout<<endl;
28.  
    }
29.  
    }
30.  
    }

这篇好文章是转载于：学新通技术网