爱奇艺-笔试刷题2018-07-19

题目描述：

/**
牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。
BubbleSort(a):
    Repeat length(a)-1 times:
        For every i from 0 to length(a) - 2:
            If a[i] > a[i+1] then:
                 Swap a[i] and a[i+1]
牛牛现在要使用上述算法对一个数组A排序。
在排序前牛牛允许执行最多k次特定操作(可以不使用完),
每次特定操作选择一个连续子数组,然后对其进行翻转,
并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,
如果牛牛选择的子数组是[2,4](注意下标从0开始),
那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,
牛牛想知道对于一个数组A在进行k次特定操作之后,
再进行上述冒泡排序最少的Swap操作次数是多少?
输入描述:
输入包括两行,
第一行包括两个正整数n和k(2 ≤ n ≤ 50, 1 ≤ k ≤ 50),表示数组的长度和允许最多的特定操作次数。
第二行n个正整数A[i](1 ≤ A[i] ≤ 1000),表示数组内的元素,以空格分割。
输出描述:
输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。
输入例子1:
3 2
2 3 1
输出例子1:
1
*/

思路如下：

dp[i][k]表示0-i这一段操作k次以内
操作后数组0-i里面得到最少的逆序数
具体更新见代码
O(nkn)

代码如下：

#include <stdio.h>
#include<iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int maxn=55;
 
 
int getCnt(vector<int> A,int x)
{
    int n=A.size(),cnt=0;
    for(int i=x; i<n; i++)
        for(int j=0; j<i; j++)
            if(A[j]>A[i])
                cnt++;
    return cnt;
}
int n,dp[maxn][maxn],k,K,i,j;
int main()
{
    scanf("%d%d",&n,&K);
    vector<int> A(n);
    for(i=0; i<n; i++)
        scanf("%d",&A[i]);
    for(i=n-1; i>=0; i--)
        for(k=0; k<=K; k++)
        {
            //0-i这一段就是tmp1
            vector<int> tmp1(A.begin(),A.begin()+i+1);
            //getCnt计算0-i这一段的逆序数
            dp[i][k]=getCnt(tmp1,i)+dp[i+1][k];
            //更新dp[i][k]
            if(k>=1)
            {
                for(j=i+1; j<n; j++)
                {
                    //在后[i+1,j]并旋转并且重新计算[0,i]段逆序数看是否能够更少
                    //看可不可以使得更少
                    vector<int> tmp2(A.begin(),A.begin()+j+1);
                    reverse(tmp2.begin()+i,tmp2.begin()+j+1);
                    dp[i][k]=min(dp[i][k],getCnt(tmp2,i)+dp[j+1][k-1]);
                }
            }
        }
    printf("%d",dp[0][K]);
}