淄博那里有做网站的,八度填写icp备案网站 接入信息,响应式网站发展,室内设计联盟论坛题目描述 多米诺骨牌有上下2个方块组成#xff0c;每个方块中有1~6个点。现有排成行的 上方块中点数之和记为S1#xff0c;下方块中点数之和记为S2#xff0c;它们的差为|S1-S2|。例如在图8-1中#xff0c;S161119#xff0c;S2153211#xff0c;|S1-S2|2。每个多米诺骨牌…题目描述 多米诺骨牌有上下2个方块组成每个方块中有1~6个点。现有排成行的 上方块中点数之和记为S1下方块中点数之和记为S2它们的差为|S1-S2|。例如在图8-1中S161119S2153211|S1-S2|2。每个多米诺骨牌可以旋转180°使得上下两个方块互换位置。 编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。 对于图中的例子只要将最后一个多米诺骨牌旋转180°可使上下2行点数之差为0。 输入输出格式 输入格式 输入文件的第一行是一个正整数n(1≤n≤1000)表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数表示多米诺骨牌上下方块中的点数a和b且1≤ab≤6。 输出格式 输出文件仅一行包含一个整数。表示求得的最小旋转次数。 输入输出样例 输入样例#14
6 1
1 5
1 3
1 2输出样例#11题解这道题是一道基础的01背包问题 决策很好想 对于一个牌 无非就是翻转或者不翻转 所以由此我们可以从决策入手 设f[i][j]k表示前i张牌构成分值j的最小次数k 则转移方程: //不反转 int difa[i]-b[i];f[i][jdifN]min(f[i][jdifN],f[i-1][jN]); //反转 difb[i]-a[i]; f[i][jdifN]min(f[i][jdifN],f[i-1][jN]1); 代码如下 #includecstdio
#includecstring
#includealgorithm
#includecstdlib
#define N 5000
using namespace std;int n,suma,sumb,a[1010],b[1010],f[1010][10005];
int ans0x7f7f7f,k0,p;int main()
{memset(f,0x7f7f7f,sizeof(f));scanf(%d,n);for(int i1;in;i){scanf(%d%d,a[i],b[i]);sumaa[i],sumbb[i];}f[0][5000]0;int maxn5*n;for(int i1;in;i)for(int j-maxn;jmaxn;j){int difa[i]-b[i];f[i][jdifN]min(f[i][jdifN],f[i-1][jN]);difb[i]-a[i];f[i][jdifN]min(f[i][jdifN],f[i-1][jN]1);}for(int jN-maxn;jmaxnN;j)if(f[n][j]!f[0][0]){if(ansabs(j-N)) ansabs(j-N),kf[n][j],pj;else if(ansabs(j-N)) kmin(f[n][j],f[n][p]);} printf(%d,k); return 0;
} 转载于:https://www.cnblogs.com/rir1715/p/6814576.html
