欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

【SSL】 多米诺骨牌

程序员文章站 2022-03-23 09:11:35
DescriptionInput输入文件的第一行是一个正整数n(1≤n≤1000),表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数a和b,且1≤a,b≤6。Output输出文件仅一行,包含一个整数。表示求得的最小旋转次数。Sample Input46 11 51 31 2Sample Output1思路设f[i][j]为前i张骨牌差值为j的最小旋转次数f[i][j]=min(f[i−1][j−a...

Description

【SSL】 多米诺骨牌

Input

输入文件的第一行是一个正整数n(1≤n≤1000),表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数a和b,且1≤a,b≤6。

Output

输出文件仅一行,包含一个整数。表示求得的最小旋转次数。

Sample Input

4						
6 1
1 5
1 3
1 2

Sample Output

思路

设f[i][j]为前i张骨牌差值为j的最小旋转次数
f[i][j]=min(f[i1][ja[i]+b[i]],f[i1][jb[i]+a[i]+1])(6n<=j<=6n,1<=i<=n)f[i][j]=min(f[i-1][j-a[i]+b[i]],f[i-1][j-b[i]+a[i]+1])(-6*n<=j<=6*n,1<=i<=n)
code:

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstdio>
using namespace std;
int f[1001][15000];
int a[1001],b[1001],n;
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>a[i]>>b[i];
  a[i]=a[i]-b[i];
 }
 for (int i=1;i<=n;i++)
 {
  for (int j=0;j<=14000;j++) f[i][j]=1207;
 }
 f[1][7000+a[1]]=0;
 f[1][7000-a[1]]=1;
 for (int i=2;i<=n;i++)
 {
  for (int j=6*n+7000;j>=-6*n+7000;j--) f[i][j]=min(f[i-1][j+a[i]]+1,f[i-1][j-a[i]]);
 }
 for (int i=0;i<=6*n;i++)
 {
  if (f[n][i+7000]<1207||f[n][7000-i]<1207)
  {
   cout<<min(f[n][i+7000],f[n][7000-i]);
   return 0;
  }
 }
    return 0;
}

本文地址:https://blog.csdn.net/weixin_49843717/article/details/108174793

相关标签: dp