锐客网

  1. 首页 > it技术 > >

【SSL】 多米诺骨牌

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
１

思路 【【SSL】 多米诺骨牌】设f[i][j]为前i张骨牌差值为j的最小旋转次数
f [ i ] [ j ] = m i n ( 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 ) 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) 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 #include #include #include #include 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<

    推荐阅读


    上一篇：利用Mock变量在ApiPost发送一个自增的参数（例如page）

    下一篇：洛谷T142270|洛谷T142270 A.「EZEC-3」造房子