我要评论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 2Sample Output
１思路
设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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论