题目
n张牌，正反两面都有数字，给初始序列。
一次操作交换相邻的两张牌并翻转这两张牌。
求问能否最后所有朝上的牌构成非减序列
2<= n<=18
题解
显然数值范围没意义，因为就算很大，离散一下也就最多36个
显然根据交换规则，把i放到j后，它的正反面是确定的
所以排列的状态数是n!，18的阶乘就不要想枚举了
这题的边界感觉也能很难想，所以有想过的一个骗分方向是迭代加深，但是估计只能骗分答案比较小，或者n比较小的点
有人贪心100%了？？ 不知道腾讯出题的人在干嘛？这样明显一堆hack点的能100%，叫那些写状压的没满的怎么想
前置知识：冒泡排序操作数 = 逆序对个数。
这题目只看操作过程中坐标的变化，实际就是在进行冒泡排序，所以我们的步数也就是 最初顺序标号变成最后顺序标号的逆序对个数
状态设计[前i个，使用的元素的state，第i个用的是下标j]
注意到state用0/1来表示是否选择，1的个数就是i，所以可以省略为[state,j]
这个状态对应的值 dp[state,j]为 已经选出的元素的逆序对的最小值
转移方程为
dp[state][j] = min(dp[state 去掉 j][for剩余可选] + state剩余部分和j构成的逆序对)
注意到state内部顺序不影响state剩余部分 和 j构成的逆序对的值
= min(dp[state 去掉 j][for剩余可选]) + state剩余部分和j构成的逆序对
所以 一个状态的最小，是从去掉最后一个的最小来的
(感觉这里局部最优/最小性证明有点绕，或者可以用归纳证？
注意保证题目限制非减序列别忘了
Code
不是我写的，链接在下方,加了点注释
1
2
3
| 作者：qin_peng
链接：https://www.nowcoder.com/discuss/417957?type=0&order=0&pos=77&page=1
来源：牛客网
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int n,a[20],b[20];
int dp[1<<20][20];
const int INF=1e9;
int main(){
I(n);
for(int i=0;i<n;i++)sc("%d",&a[i]);
for(int i=0;i<n;i++)sc("%d",&b[i]);
for(int i=1;i<n;i+=2)swap(a[i],b[i]);
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
dp[i][j]=INF;
}
}
for(int i=0;i<n;i++)dp[1<<i][i]=0;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(dp[i][j]==INF)continue;
for(int k=0;k<n;k++){
if(i>>k&1)continue;
int x=__builtin_popcount(i)&1;
if(x){
if(b[k]<a[j])continue;
}else{
if(a[k]<b[j])continue;
}
int ans=0;
for(int l=k+1;l<n;l++){
if(i>>l&1)ans++;
}
dp[i|1<<k][k]=min(dp[i|1<<k][k],dp[i][j]+ans);
}
}
}
int ans=INF;
for(int i=0;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]);
if(ans==INF)O(-1);
else O(ans);
}
|
总结
很早看到18 就条件反射的想2的n次方
看到交换两个也想到了逆序对和冒泡
但没想出最后的状态以及转移，果然设计状态有点难啊，我好菜哇
大概技术总结的话应该是 除了最简单的状态，还有一种是[state][末尾选择]，这样的话能保证性质就行，如这里的末尾选择就是用来保证 非减少的