【DP】ドミノ

テーマ
[外鎖写真の転載失敗(img-FH 2 WZOZ-152483000261)(http://10.156.17.250/JudgeOnline/image/1632.gif =490 x 330)]
入力
入力ファイルの最初の行は正の整数n(1≦n≦1000)で、ドミノの数を表します.次のn行はn個のドミノの点数を表します.各行にはスペースで仕切られた正の整数が二つあり、ドミノの上から下のブロックの中の点数aとbを表しています.しかも1≦a、b≦6です.
出力
出力ファイルは1行のみで、整数が含まれています.求められた最小回転回数を表します.
入力サンプル
4 6 1 1 5 1 3 1 2
出力サンプル
1
問題を解く構想
少なくとも回転数を考えずに、上下の2行の絶対値差を最小にする案を探してもいいです.前のI枚の牌ができる最小の差をF[I]で表して、動的な企画方程式を作って問題を解決したいと考える人がいるかもしれません.しかし、よく考えてみると、この問題はこのような方法で最適性原理を満たしていないということが分かります.このような形式の動的企画は実は欲張りで、反例があります.カードの点数の範囲が小さいことに気づいて、0から6までしか取れません.ですから、前のI枚のカルタが上下差Jという案をF[I,J]で表してもいいです.そこで、動的転送方程式:f[i,j]=f[I–1,j–(a[i]–b[i])]o r f[i–1,j–(b[i]]]=f[i,j]=f[I–1,j–i–f[i]]or f[i–i–i–i–i–1,j–i–1,j–i–a[i]]]]]]f[i–f[i–f[i–i–f[i–i–1,j–f[i–i–i–i–i–i–i–i–i–i–i–1,j–1,j–a[i]]のうちA[I]、B[I]I番目の牌の最初の上下の両面の点数をそれぞれ表します.対応する二つの移行方式はそれぞれI番目の牌のめくり方とI番目の牌が動かない場合を表します.境界:f[0,0]=T r u境界:f[0,0]=True境界:f[0,0]=True現在の問題は、どうやって一番古い骨板の数を求めるかです.f配列を再定義して、前のI枚のカルタの差jをf[i,j]で表します.したがって、式を挙げると、f[i,j]=m i i n(f[i–1,j–(a[i]–b[i])))、f[i–1,j–1、–i–i–i–a[i]、+1)f[i,j]=m i n(f[i–1,j–(a[i]–b[i]–b[i)))))))))))))、f[i–a[i–a[i–a[i–a[i]]、、、、、、、(((((–1–a–a[i]–a[i]]–a[i]]–a[i–a[i]]]]j–(b[i]–a[i]]]+1)
注意
境界:f[0,0]=0境界:f[0,0]=0境界:f[0,0]=0前のi枚の骨板がめくれる最小差分値は、min-abs(a[i]–b[i]より小さくはなく、最大差分値はmax+abs(a[i]–b[i]より大きくはない.)
プログラムは以下の通りです

#include
#include
#include
#define M 6000//  
using namespace std;
int n,a[1001],b[1001],f[1001][M*2],k;
int main()
{
	memset(f,127/3,sizeof(f));
	scanf("%d",&n);
	f[0][M]=0;//   
	for(int i=1;i<=n;i++)
	  scanf("%d%d",&a[i],&b[i]);
	  for(int i=1;i<=n;i++)
	  {
	  	for(int j=1;j<=2*M;j++)
	  	{
	  		f[i][j]=min(f[i-1][j-a[i]+b[i]],f[i-1][j+a[i]-b[i]]+1);//           i   ，                  ，           i，          1

	  	}
	  }
	  k=0;// k 0  
	  if((f[n][M+k]==f[0][1])&&(f[n][M-k]==f[0][1])) k++;// f[0][1]        k
	  printf("%d",min(f[n][M+k],f[n][M-k]));//    
	return 0;
}