hdu3045

在做了几个入门的斜率dp题之后写这个题,其实这个题的方程跟之前的入门题hdu3507差不多 ,

dp[i] = min(dp[i] , dp[j] + (sum[i] - sum[j]) - (i-j) *(num[i+1]) ) ; {0 <= j <= i - T} 可以看出来其实基本上没什么不同,唯一有区别的是j的取值范围.0到i-T 这是我一开始写的版本

#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, m , 1 LONG num[400200] ; LONG dp[450010] ; LONG que[410000] ; LONG Sum[410000] ; LONG Up(LONG j, LONG k) { return (dp[j] - dp[k]) - (Sum[j] - Sum[k]) + j * num[j+1] - k*num[k+1] ; } LONG Down(LONG j , LONG k) { return num[j+1] - num[k+1] ; } int main() { //freopen("/home/weyoung/桌面/inn","r",stdin); int T; int n ; while( cin>> n >>T) { clr1(dp) ; dp[0] = 0 ; Sum[0] = 0 ; for(int i =1; i<= n ; ++i) scanf("%lld",&num[i]) ; sort(num+1 , num + n + 1 ) ; for(int i = 1;i<=n ; ++i) Sum[i] = Sum[i - 1] + num[i] ; int head = 1, tail = 1; que[1] = 0 ; for(int i = 1; i<= n ; ++i) { if(i < T ) continue ; while(1) { if(head >= tail )break ; if( que[head+1] <= i-T && Up(que[head+1] , que[head] )<= i * Down(que[head+1], que[head])) head ++ ; else break ; } int t = que[head] ; dp[i] = dp[t] + (Sum[i] - Sum[t]) - (i - t) *num[t+1] ; while(1) { if(head >= tail) break ; if(Up(i,que[tail]) * Down(que[tail] , que[tail-1]) <= Up(que[tail] , que[tail-1]) * Down(i ,que[tail])) tail -- ; else break ; } que[++tail] = i ; } // for(int i =1; i<= n ; ++i) // printf("%lld ",dp[i]); cout<<endl; cout<<dp[n]<<endl; } }

这样写看起来好像也没什么地方不对,但是有个重要的问题,当我们在往队列中插入元素的时候,要满足g[i,j] > g[j , k] ,而这个题目j的取值范围是i-T,但是这份代码里,实际上往队列里插的是i,这就导致了当前队列中有些元素不满足g[i,j] > g[j.k]但是可以满足g[i-T,j] > g[j,k] ,把有些有效元素抛出了解集,最后导致转移不充分,结果偏大. 正解应该是这样

#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const LONG INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, m , 1 LONG num[400200] ; LONG dp[450010] ; LONG que[410000] ; LONG Sum[410000] ; LONG Up(LONG j, LONG k) { return (dp[j] - dp[k]) - (Sum[j] - Sum[k]) + j * num[j+1] - k*num[k+1] ; } LONG Down(LONG j , LONG k) { return num[j+1] - num[k+1] ; } int main() { LONG n , T ; while( cin>> n >>T) { dp[0] = 0 ; Sum[0] = 0 ; for(LONG i =1; i<= n ; ++i) scanf("%lld",&num[i]) ; sort(num + 1 , num + n + 1 ) ; for(LONG i = 1;i<=n ; ++i) Sum[i] = Sum[i - 1] + num[i] ; LONG head = 1, tail = 1; que[1] = 0 ; for(LONG i = T; i<= n ; ++i) { LONG judge = 0; while(1) { if(head >= tail )break ; if( Up(que[head+1] , que[head] )<= i * Down(que[head+1], que[head])) head ++ ; else break ; } LONG t = que[head] ; dp[i] = dp[t] + (Sum[i] - Sum[t]) - (i - t) *num[t+1] ; int p = i - T + 1; if(p < T) continue; // 注意这里 while(1) { if(head >= tail) break ; if(Up(p,que[tail]) * Down(que[tail] , que[tail-1]) <= Up(que[tail] , que[tail-1]) * Down(p ,que[tail])) tail -- ; else break ; } que[++tail] = p; } cout<<dp[n]<<endl; } }