【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
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
1
思路
设f[i][j]为前i张骨牌差值为j的最小旋转次数
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