[CEOI 1997] 多米诺骨牌 题解

[CEOI 1997] 多米诺骨牌 题解题目传送门——请务必读好题目这题让求点数和之差最小的旋转次数因为这个差需要取绝对值所以转移很难。带绝对值转移难那干脆把绝对值扔了d p i , j dp_{i,j}dpi,j​表示前i ii个骨牌差值为j jj的最少旋转次数。状态转移d p i , j min ⁡ ( d p i − 1 , j d i 1 , d p i − 1 , j − d i ) dp_{i,j} \min(dp_{i-1,jd_i} 1, dp_{i-1,j-d_i})dpi,j​min(dpi−1,jdi​​1,dpi−1,j−di​​)其中d i d_idi​表示a i − b i a_i - b_iai​−bi​。由于我们扔掉了绝对值所以我们可以在最后遍历的时候考虑上负差值。参考代码#includeiostream#includecstringconstexprintrev5000;usingnamespacestd;intn;inta[1010],b[1010];intdp[1010][10010];intmain(){memset(dp,0x3f,sizeof(dp));cin.tie(0)-sync_with_stdio(false);cinn;for(inti1;in;i){cina[i]b[i];}dp[0][0rev]0;for(inti1;in;i){for(intj-5000;j5000;j){//枚举差值intda[i]-b[i];//计算当前差值if(jdrev0dp[i-1][jdrev]^0x3f3f3f3f)dp[i][jrev]min(dp[i][jrev],dp[i-1][jdrev]1);//如果可以就转移if(j-drev0dp[i-1][j-drev]^0x3f3f3f3f)dp[i][jrev]min(dp[i][jrev],dp[i-1][j-drev]);}}for(inti0;i5000;i){intans0x3f3f3f3f;if(dp[n][irev]!0x3f3f3f3f)ansmin(ans,dp[n][irev]);if(dp[n][rev-i]!0x3f3f3f3f)ansmin(ans,dp[n][rev-i]);if(ans!0x3f3f3f3f){coutans;return0;}}}by lonys