【Lanqiao】数位翻转

题目：

思路：

写蓝桥不能不写dp，就像....

 题目数据给的不大，所以我们可以考虑一种 n*m 的做法，那么对于这种题目可以想到的是用dp来写，但是如何构造转移方程与状态是个难事

由于这题对于任意一个数我们有两种可能，即翻转or不翻转，那么肯定要有一维代表这个，同时我们还有一个数m，我们可以决定一共翻转m个，所以还可以用一维表示这个，那么我们就能想到一个暴力的dp，我们定义 dp[i][j][k] 为前 i 个数一共翻转了 j 个区间且当前数是否翻转了

对于 dp[i][j][0]，即当前没翻转，那么可以从哪里转移呢？显然只有两种转移，即 dp[i-1][j][0] 和 dp[i-1][j][1] ，因为我们没翻转，所以选的区间数不会变，但是上一个数可以翻转or不翻转

对于 dp[i][j][1]，即我们此刻翻转，那么就有两种情况，一个是前面翻转了，一个是前面没反转，如果前面没翻转，那么就是 dp[i-1][j-1][0]，因为我们此刻增加了一个新的翻转区间，所以是 j - 1，如果前面翻转了，那么就还分两种情况：接着上一个区间，那就是 dp[i-1][j][1]，此时新开一个区间，那就是 dp[i-1][j-1][1]，不够按理来说第二种是不会出现的，明显不优

至此我们讨论完毕，然后dp即可，我们这里可以将转移方程中的转移的奉献变为 b[i] - a[i]，这样的话能少写一点，并且更直观，具体看代码

（还学到了max可以用花括号一次max好几个元素）

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define PII pair<int,int>int a[1005];
int b[1005];
//题目说的操作
int f(int x)
{int res = 0;int mxbit = 0;for (int i = 31; i >= 0; i--){if ((x >> i) & 1){mxbit = i;break;}}for (int i = 31; i >= 0; i--){if ((x >> i) & 1){res += 1LL << (mxbit - i);}}return res;
}
//前i个数 翻转了j个区间 且第i位 翻or不翻 转
int dp[1005][1005][2];
void solve()
{int n, m;cin >> n >> m;int res = 0;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = f(a[i]) - a[i];res += a[i];}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j][0] = max(dp[i - 1][j][1], dp[i - 1][j][0]);dp[i][j][1] = max({ dp[i - 1][j - 1][0],dp[i - 1][j][1],dp[i - 1][j - 1][1] }) + b[i];}}int mx = 0;//枚举选多少个区间 ifor (int i = 1; i <= m; i++){mx = max({ mx,dp[n][i][0] ,dp[n][i][1] });}cout << res + mx;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}