动态规划之四边形不等式和斜率优化

1、1四边形不等式优化 对于转移mpj =IJ4-m( 川 + 柿 J如果满足:当函敦 附滿爼Mti；j+4ff/swrwfr,j ；£冷 称神满足四辿羽不势式存在sij的转移：slj=maxk | mlj=mlrk-l+inkj+wlj 最后转移：踪上蔚述谨问題的抉策现町具有单fl性.于是优化后肘状応转移力程为E时心 min|阀fl用+就& +ijs(»J=k网上文所述,优化启怖鼻法时闾貝競度为O(n*p).1.1例题：hdu 3480划分问题Divisio nProblem Descripti onLittle D is really in terested in

2、the theorem of sets recen tly. There' s a problem that con fusedlong time.Let T be a set of integers. Let the MIN be the minimum integer in T and MAX be the maximum,then the cost of set T if defi ned as (MAX-MIN)A2. Now give n an in teger set S, we want to findout M subsets S1, S2,SM of S, such

3、thatand the total cost of each subset is mini mal.In putThe in put contains multiple test cases.In the first line of the in put there 'an in teger T which is the nu mber of test cases. Then the description of T test cases will be given.For any test case, the first line contains two integers N (

4、W10,000) and M ( w 5,000). N is the nu mber of eleme nts in S (may be duplicated). M is the nu mber of subsets that we want to get. I n the n ext line, there will be N in tegers giv ing set S.OutputFor each test case, output one line containing exactly one in teger, the mini mal total cost. Take a l

5、ook at the sample output for format.Sample In put23 21 2 44 24 7 10 1Sample OutputCase 1: 1Case 2: 1分析：1) dpij表示前i个数字，分成j份的最小值2) dpij=min(dpkj-1+wk+1j)(i<=k<j);3) 判断wij(i和j之间的最大和最小的差的平方)是否满足则是四边形不等式，直接套转移即可4)代码：#in clude <cstdio>#in clude <cstri ng>#i nclude <algorithm> using

6、 n amespace std;#define N 10001#defi ne M 5001con st int INF = 0x7fffffff;in li ne int sqr(i nt x) return x * x;int n, m;int aN;int dpNM;int sNM;in t cal() if (n <= m) return 0; sort(a + 1, a + 1 + n);for (int i = 0; i <= n; +i)for (int j = 0; j <= m; +j) dpij = -1;dp00 = 0;for (int i = 1;

7、i <= n; +i) int maxj = min(i, m);int mn = INF , mk;for (int k = 0; k < i; +k) if (dpkmaxj - 1 != -1) int tmp = dpkmaxj - 1 + sqr(ai - ak + 1); if (tmp < mn) mn = tmp; mk = k; dpimaxj = mn; simaxj = mk;for (int j = maxj - 1; j >= 1; -j) int mn = INF , mk;for (int k = si - 1j; k <= sij

8、+ 1; +k) if (dpkj - 1 != -1) int tmp = dpkj - 1 + sqr(ai - ak + 1);if (tmp < mn) mn = tmp; mk = k;dpij = mn;sij = mk;return (int)dpnm;int main() int t, cas = 0;scanf("%d", &t);while (t-) scanf("%d %d", &n, &m);for (int i = 1; i <= n; +i)scanf("%d",&

9、;ai); printf("Case %d: %dn", +cas, cal();return 0;1.2 例题 hdu 3506 合并问题Monkey PartyProblem DescriptionFar away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate

10、Crazy Bananas Day. But the little monkeys don't know each other, so as the king, SDH must do something.Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:1.every

11、time, he can only introduce one monkey and one of this monkey's neighbor.2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;3.e

12、ach little monkey knows himself;In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.InputThere is several test cases. In each case, the first line is n(1w n w 1000), which is the nummonkeys. The next line contains n positive inte

13、gers(less than 1000), means the making friendstime(in order, the first one and the last one are neighbors). The input is end of file.OutputFor each case, you should print a line giving the mininal time SDH needs on introducing.Sample Input85 2 4 7 6 1 3 9Sample Output105代码：#include <cstdio>#in

14、clude <cstring>#include <algorithm>using namespace std;#define inf 0x3fffffff#define N 2005#define M 2005int min(int x,int y)if(x>y)return y;else return x;int n, m;int aN;int dpNM;int sNM;int wNN;int cal() int i,j,k,len;for(i=0;i<=n+n;i+)dpii=0,sii=i;for(len = 2; len <=n; len+)

15、for(i=1;i<=n+n;i+) j=i+len-1; if(j>n+n)continue; dpij=inf; for(k=sij-1;k<=si+1j;k+) int tmp=wij+dpik+dpk+1j; if(dpij>tmp) dpij=tmp;sij=k;int Min=inf;for(i=1;i<=n;i+)if(dpii+n-1<Min)Min=dpii+n-1;return Min;void MakeW()int i,j;memset(w,0,sizeof(w); for(i=1;i<=n+n;i+) wii=ai; for(j=i+1;j<=n+n;j+) wij=wij-1+aj;