【Array】

【问题描述】

给定2个正整数序列A1,A2,序列长度分别为L1,L2。

你可以进行一下的一次操作:

1.选择两个数K1,K2(1≤K1≤L1,1≤K2≤L2);

2.移去A1中最后K1个数,得到这K1个数的和S1,L1对应减少K1

3.移去A2中最后K2个数,得到这K2个数的和S2,L2对应减少K2;

此次操作的费用为(S1-K1)*(S2-K2)。

进行以上操作直至两个序列都为空,求最小的费用总和。

注意:序列为空当且仅当两个序列同时为空。

【输入格式】

第一行是两个正整数L1和L2,表示A1和A2的长度。

第二行L1个整数,表示序列A1

第三行L2个整数,表示序列A2

【输出格式】

输出一个整数,表示最小费用。

【输入样例】

3 2

1 2 3

1 2

【输出样例】

2

【样例说明】

第一次选取K1=1 K2=1 费用为(3-1)*(2-1)=2.

第二次选取K1=2 K2=1 费用为(1+2-2)*(1-1)=0.

所以,总费用为2.

【数据范围】

对100%的输入数据:1≤L1,L2,A1[1~L1],A2[1~L2]≤5000

空间限制:256MB(128MB理论不可以过除非滚动数组但是实际上数据太水压在int内还是能过的23333)

看题就知道是大DP

其实S1-K1或者S2-K2是可以预处理出来的~反正都要减掉长度,读入的时候-1不就完啦~

比如1 3 7 选后面2个就是10-2=8 先开始读入变成0 2 6 后缀和就是8了

于是设dp[i][j]表示序列A1剩i个数,序列A2剩j个数的最优解。

显然容易想到dp[i-k1][j-k2]=dp[i][j]+sum1*sum2(sum1,sum2是sum1-k1,sum2-k2经过读入-1处理过的)

好了 单调队列搞一搞就有40分了,然并卵。

进一步分解sum1*sum2=A1[i]*A2[j]+A1[i]*A2[j-1]+……+A1[i]*A2[j-k2+1]+A[i-1]*A2[j]+……+A1[i-k1+1]*A2[j-k2+1]

注意一个很简单的数学规律:(a+b)*(c+d)>ac+bd

所以比如

A1:1 2 3

A2:1 2

在一次选择中选2 2下一次选1 1肯定比一次选1 2和1 2更优,所以最好的情况就是一个一个分

于是进一步乱搞得转移方程:dp[i][j]=min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])+A1[i+1]*A2[j+1]

做完了。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*