BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Tue Sep 26 16:36:35 2006) 提到: 输入一个Matrix,是［n］［２］(n是输入的)：比如 up down ３４２５４３５１２１把矩阵的两列看成up,down两部分．题目要求：可以自由地把同一行的up,down的数字互换，要求用最小的互换次数使得 |所有up的数字和－所有down的数字和|最小．我自己用的Dp： up[i][j]表示第i行到第j行按最佳方案时所有up的重量和； down[i][j]表示第i行到第j行按最佳方案时所有down的重量和； distance[i][j]按最佳方案时最优差值; 不难写出状态转移方程: for:k=i+1 to j-1; temp=MIN(up[i][k]-down[j][k]+up[k+1][j]-down[k+1][j],up[i][k]+down[k+1][j]-down[j][k]-up[k+1][j]); ／／如果这里up[i][k]-down[j][k]+up[k+1][j]-down[k+1][j]＞up[i][k]+down[k+1][j]-down[j][k]-up[k+1][j]就表示需要翻转； count++; if(distance[i][j]>temp) distance[i][j]=temp; 其中up[i][i]=dataup[i],down[i][i]=datadown[i](初始化); 最后输出count就可以了．．．但是这样求好象不是最小翻转次数，汗．．求一个好算法．．． ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Tue Sep 26 16:39:10 2006) 提到: poj1717,背包DP。 ☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Tue Sep 26 16:40:07 2006) 提到: 希望具体点．． ☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Tue Sep 26 16:41:09 2006) 提到: 还有啊，啥子叫多米诺性质？ ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Tue Sep 26 16:46:47 2006) 提到: 没听说过多米诺性质，这个题似乎也扯不上关系 dp[i][j]，表示前 i 组up部分的和为j的最少翻转次数。 n比较大的话为了避免超内存，可以考虑滚动数组。。 ☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Tue Sep 26 16:55:08 2006) 提到: dp[i][j]=MIN(dp[i][j-Matrix[i][0]],dp[i-1][j+Matrix[i][0]],dp[i][j+Matrix[i][1]]+1) 状态转移方程是这个吗？ ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Tue Sep 26 16:58:01 2006) 提到: 好像吧，以前做的。有点忘了。 ☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Tue Sep 26 17:00:18 2006) 提到: 其实我感觉是写错了，我再捣鼓捣鼓，应该快出来了，唉．谢谢．

[合集] poj1717 动态规划，据说考一个多米诺性质