https://www.cnblogs.com/violet-acmer/p/9852294.html
参考资料:
[1]:https://blog.csdn.net/Darost/article/details/52517823
题解:
对于一个牌,无非就是翻转或者不翻转这两种情况,所以由此我们可以从决策入手
设dp[i][j]为前i个骨牌差值为j的最小翻牌次数
初始值全部赋值为INF;
然后f[1][a[1]-b[1]]=0, f[1][b[1]-a[i]]=1;对应于第一张牌不翻和翻
状态转移方程:
f[i][j] = min(f[i-1][j-(a[i]-b[i])], f[i-1][j-(b[i]-a[i])]+1)]分别对应于不翻和翻
由于有负数,要加上一个较大的中间数把所有的值转为正数,然后找答案在dp[n]里找,从较大的中间数开始双向查找,最早找到的就是答案。
学习笔记:
此题难点在于状态转移方程的查找。
dp[ ][ ]的作用很巧妙,是我不曾想到的,初始思路只知道一个暴力,就是枚举所有的可能,从中查找最优解,时间复杂度高达O(2^n),指定不能高效求解。
算法之路还很长,一步一步来吧
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
const int maxn=+; int n;
int a[maxn],b[maxn];
int dp[maxn][*maxn];
int mid=;//中间数 void Solve()
{
dp[][a[]-b[]+mid]=,dp[][b[]-a[]+mid]=;
for(int i=;i <= n;++i)
{
for(int j=-*n;j <= *n;++j)//查找dp[i][-5n,....,5n]的最优解
{
dp[i][j+mid]=min(dp[i][j+mid],dp[i-][j-(a[i]-b[i])+mid]);
dp[i][j+mid]=min(dp[i][j+mid],dp[i-][j-(b[i]-a[i])+mid]+);
}
}
for(int i=mid,j=mid;i <= *mid || j >= ;++i,--j)
if(dp[n][i] != INF)
{
printf("%d\n",dp[n][i]);
break;
}
else if(dp[n][j] != INF)
{
printf("%d\n",dp[n][j]);
break;
} }
int main()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d%d",a+i,b+i);
mem(dp,INF);
Solve();
}