G. Sorting Pancakes
题意描述:
把一个数组a[],变成一个非递增的数组,对于当前下标i,要么从左边-1,要么从右边-1,加到a[i]上。问需要的最少操纵数。
思路:
可以发现不满足后效性,无法进行线性递推求解,因为对于当前下边为i的点,既可以从左边取到一个1,又可以从右边取到一个1.
首先需要确定一个结论。
如果数组a[]—>数组b[],那么总共的操纵次数为$$\sum_{i = 1} ^ {n} abs(suma[i] - sumb[i])$$
可以发现假设当前位置i之前已经和数组b相匹配,那么如果suma[i] > sumb[i],说明a[i]多的值要挪到后边去,
如果suma[i] < sumb[i],说明a[i]中少的值需要从后边补
可以发现状态定义需要维护数组b[]的前缀和,且因为要保证非递增需要维护以当前位置结尾的值
朴素方程f[i][j][k]:数组a[]变为b中前i个数且和为j,且其中最后一个数为k的集合
属性:min
$$f[i][j][k] = min(f[i - 1][j - k][t] + abs(sum[i] - j)) $$
其中t∈[k, j - k]
虽然看似四重for循环,但是跑的贼快。。时间复杂度未知。 但是观察第三个和第四个for循环还是可以进行优化.
打表可以发现
j = 0, k = 0,kk∈[0,0]
j = 1, k = 0,kk∈[0,1]
j = 2, k = 0,kk∈[0,2]
j = 2, k = 1,kk∈[1,1]
........
可以发现假设k倒着枚举,那么包含的范围只有越来越大,那么只需要倒着枚举k,维护[l,r]中minn即可(详细请看代码)
/* Time:264ms
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 300;
typedef pair <int, int> PII;
int a[maxn], f[maxn][maxn][maxn], sum[maxn];
int main() // n ^ 4
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1 ; i <= n ; i ++)
scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
for(int i = 0 ; i <= n ; i ++)
{
for(int j = 0 ; j <= m ; j ++)
{
for(int k = 0 ; k <= m ; k ++)
f[i][j][k] = INF;
}
}
for(int i = 0 ; i <= m ; i ++)
f[1][i][i] = abs(sum[1] - i);
for(int i = 2 ; i <= n ; i ++)
{
for(int j = 0 ; j <= m ; j ++)
{
for(int k = 0 ; k <= j / 2; k ++)
{
for(int kk = k ; kk <= (j - k) ; kk ++)
{
f[i][j][k] = min(f[i][j][k], f[i - 1][j - k][kk] + abs(sum[i] - j));
}
}
}
}
int res = INF;
for(int i = 0 ; i <= m ; i ++)
res = min(res, f[n][m][i]);
printf("%d\n",res);
return 0;
}
优化代码
/* Time: 46ms
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 300;
typedef pair <int, int> PII;
int a[maxn], f[maxn][maxn][maxn], sum[maxn];
int main() // n ^ 4
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1 ; i <= n ; i ++)
scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
for(int i = 0 ; i <= n ; i ++)
{
for(int j = 0 ; j <= m ; j ++)
{
for(int k = 0 ; k <= m ; k ++)
f[i][j][k] = INF;
}
}
for(int i = 0 ; i <= m ; i ++)
f[1][i][i] = abs(sum[1] - i);
for(int i = 2 ; i <= n ; i ++)
{
for(int j = 0 ; j <= m ; j ++)
{
int l, r;
int minn = INF;
if((j + 1) % 2 == 0) //
l = j / 2, r = (j / 2) + 1;
else
l = j / 2, r = j / 2;// f[2][1][0]
for(int k = j / 2 ; k >= 0 ; k --)
{
if(l >= 0)
minn = min({minn, f[i - 1][j - k][l] + abs(sum[i] - j)});
if(r <= j)
minn = min({minn, f[i - 1][j - k][r] + abs(sum[i] - j)});
f[i][j][k] = min(f[i][j][k], minn);
// printf("%d %d %d %d\n", i, j, k, f[i][j][k]);
l --, r ++;
}
}
}
int res = INF;
for(int i = 0 ; i <= m ; i ++)
res = min(res, f[n][m][i]);
printf("%d\n",res);
return 0;
}