锐客网

  1. 首页 > it技术 > >

#|牛客编程巅峰赛S1第12场 王者B-上上下下（DP）

dp#牛客巅峰赛基础dp

题目链接：https://ac.nowcoder.com/acm/contest/6916/B
博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13512246.html
题目描述 牛牛是一位优秀的程序员。最近，牛牛在的公司要办年会了。
牛牛所在的组要表演一个比较有意思的大合唱，程序员们站在第一排，产品经理们站在第二排。为了让年会节目更有吸引力，牛牛在设计站位上下了功夫：从左往右，程序员们由高到矮进行站位，而产品经理们则按由矮到高进行站位，两个队列的上下场方向也不一样，这样从上场、演唱到下场，整个队列看起来就像一个波浪开合，非常有趣。
牛牛他们排练完就回去工作了，转眼就来到了年会当天。当大家换上了表演用的服装后，牛牛傻了眼：之前排练的时候大家穿的都是自己的鞋，这下统一更换成演出用的鞋之后，原来两个排好的队列不再按身高有序了！然而，表演马上就要开始了，由于站位和演出效果有关，大家的站位又不能进行调整，这可怎么办？
聪明的牛牛想到了一个补救办法：如果能让相对站在同一列的产品经理和程序员互换位置，最后也能满足从左往右第一排从高到矮，第二排从矮到高，那也能满足演出效果。然而，就在这个关头，牛牛被叫去核对音乐和灯光了，他只好把这个任务交给你。他会把现在第一排和第二排的身高数据给你，请你告诉他最少需要交换几对演出成员才能满足之前的要求。如果怎么交换都不能满足，请你返回 -1。
输入
[5,4,3,2,1],[1,2,3,4,5]
输出
0
说明
显然，这个排列已经满足要求，不需要交换。
输入
[1,2,3,4,5],[5,4,3,2,1]
输出
4
输入
[3,2,1],[1,3,3]
输出
-1
说明
别忘了如果怎么交换都不能满足要求，你应该返回 -1。
备注:
注意，本题中的高矮关系为严格大于小于关系，即 [1,2,3] 可以看作由矮到高，但是 [1,3,3] 不行。
数据范围：

  • 对于 20% 的数据， 1 ≤ N ≤ 16 1\le N\le 16 1≤N≤16
  • 对于 60% 的数据， 1 ≤ N ≤ 1 0 3 1\le N\le 10^3 1≤N≤103
  • 对于 100% 的数据， 1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1≤N≤105
对于 100% 的数据，两个数组的大小均恰好为 ，且两个数组{ a i } , { b i } \{a_i\}, \{b_i\} {ai?},{bi?}的元素均满足1 ≤ a i , b i ≤ 1 0 9 1\le a_i, b_i\le10^9 1≤ai?,bi?≤109 。
emmmm,一个很明显的DP，他肯定有一个状态来枚举每一位，再来一个状态来枚举每一位换不换，那么就可以得到 d p [ n ] [ 0 / 1 ] dp[n][0/1] dp[n][0/1]这个dp状态了。接下来就是转移方程了，很明显每个位置有换与不换两种情况，我们分开讨论，对于该位置不换的情况，也就是从上一个状态转移到 d p [ i ] [ 0 ] dp[i][0] dp[i][0]，那么我们还得看看上一个状态的情况，如果我们是从上一个不换状态转移过来的，那么其必然有条件： f i r s t R o w [ i ? 1 ] > f i r s t R o w [ i ]&s e c o n d R o w [ i ? 1 ] < s e c o n d R o w [ i ] firstRow[i-1]>firstRow[i]\ \& \ secondRow[i-1]firstRow[i?1]>firstRow[i] & secondRow[i?1]
if (firstRow[i-1]>firstRow[i] && secondRow[i-1][i]) dp[i][0]=min(dp[i][0],dp[i-1][0]); if (secondRow[i-1]>firstRow[i] && firstRow[i-1][i]) dp[i][0]=min(dp[i][0],dp[i-1][1]); if (firstRow[i-1]>secondRow[i] && secondRow[i-1]secondRow[i] && firstRow[i-1]

于是此题结束。
【#|牛客编程巅峰赛S1第12场 王者B-上上下下（DP）】以下是AC代码：
const int mac=1e5+10; const int inf=1e9+10; int dp[mac][2]; class Solution { public: /** * 计算最小交换次数 * @param firstRow int整型vector 第一行的身高数据 * @param secondRow int整型vector 第二行的身高数据 * @return int整型 */ int arrange(vector& firstRow, vector& secondRow) { int n=firstRow.size(); for (int i=0; i<=n; i++) dp[i][0]=dp[i][1]=inf; dp[0][0]=0; dp[0][1]=1; for (int i=1; ifirstRow[i] && secondRow[i-1][i]) dp[i][0]=min(dp[i][0],dp[i-1][0]); if (secondRow[i-1]>firstRow[i] && firstRow[i-1][i]) dp[i][0]=min(dp[i][0],dp[i-1][1]); if (firstRow[i-1]>secondRow[i] && secondRow[i-1]secondRow[i] && firstRow[i-1]=inf) return -1; return ans; } };

    推荐阅读


    上一篇：扩展欧几里得例题(luogu_1082)

    下一篇：【力扣】搜索插入位置