pku 3998 Land Division DP斜率优化

题意:
n个点,用水平线或者竖直线划分成k条,要求平均差最小,平均差为每条中点的个数减去n/k的绝对值。
解法:
首先一看就是个DP,与处理不说了,用水平扫描线、竖直扫描线将同一直线上的点压缩成一个带权值的点,然后DP
这题重要的是DP降维
观察DP方程
dp[i]=min{dp[j]+|sum[i]-sum[j]-average|}
这里就要分成两部分讨论
1、当sum[i]-sum[j]>average时
dp[i]=min{dp[j]+sum[i]-sum[j]-average}
这就是一个变量“打擂台”的问题,从前向后扫,维护一个dp[j]-sum[j]的最小值即可。
2、当sum[i]-sum[j]<average时
dp[i]=min{dp[j]+average-sum[i]+sum[j]}
这里打擂台就不行了,因为区间是移动着的。开始偷懒,直接用STL的set动态维护一个dp[j]+sum[j]的最小值。。果断TLE。。汗。。
木办法。。化简方程吧
把sum[j]看作横坐标,dp[j]看作纵坐标,转化为斜率优化问题
dp[j]=-sum[j]+sum[i]-average+dp[i]
令sum[i]-average+dp[i]=A
方程化为
dp[j]=-sum[j]+A
为了让A最小,就是找到个j,使得dp[j]+sum[j]最小,然后就是斜率优化的经典方法了,用栈队列
当dp[k]+sum[k]>dp[j]+sum[j],j>k的时候,k退栈,然后将j压栈
在栈的底端,将不符合要求的状态,即sum[i]-sum[j]>average,i>j的队头状态j给出队。这样,队头的元素就为最优值
所有元素顶多进队一次,出队一次,复杂度O(n)
总复杂度为O(k*m)

不知道怎么回事。。在POJ上死都TLE。。本机秒解,HDU500MS,可能分数类写的有点搓了。。把代码贴出来,大家看看哪里能修正修正。。。好想好想把poj给过了啊。

  1# include <cstdio>
  2using namespace std;
  3# include <vector>
  4# include <algorithm>
  5# include <utility>
  6# include <functional>
  7# include <map>
  8# include <cstring>
  9# define abs(num) ((num)>0?(num):-(num))
 10# define eps 1e-6
 11struct func
 12{
 13    int up,down;
 14    func(){}
 15    func(int num):up(num),down(1){}
 16    int gcd(int a,int b)
 17    {
 18        if(!b) return a;
 19        else return gcd(b,a%b);
 20    }

 21    void simple()
 22    {
 23        int t=gcd(abs(up),abs(down));
 24        up/=t;
 25        down/=t;
 26        if(down<0) up*=-1,down*=-1;
 27    }

 28    func operator+(const func &pos)
 29    {
 30        func res;
 31        res.down=down*pos.down;
 32        res.up=up*pos.down+pos.up*down;
 33        res.simple();
 34        return res;
 35    }

 36    func operator-(const func &pos)
 37    {
 38        func res;
 39        res.down=down*pos.down;
 40        res.up=up*pos.down-pos.up*down;
 41        res.simple();
 42        return res;
 43    }

 44    bool operator<(const func &pos) const
 45    {
 46        return up*pos.down<pos.up*down;
 47    }

 48    bool operator==(const func &pos) const
 49    {
 50        return up==pos.up&&down==pos.down;
 51    }

 52    bool operator!=(const func &pos) const
 53    {
 54        return up!=pos.up||down!=pos.down;
 55    }

 56    bool operator<=(const func &pos) const
 57    {
 58        return *this<pos||*this==pos;
 59    }

 60
 61}
;
 62int data[100000],de;
 63func dp[10][100000];
 64func aver;
 65int k;
 66int q[100000];
 67func num[100000];
 68struct cmp
 69{
 70    bool operator()(const pair<int,int> &a,const pair<int,int> &b) const
 71    {
 72        if(dp[a.first][a.second]+func(data[a.second])!=dp[b.first][b.second]+func(data[b.second]))
 73            return dp[a.first][a.second]+func(data[a.second])<dp[b.first][b.second]+func(data[b.second]);
 74        else return a.second<b.second;
 75    }

 76}
;
 77func min(func a,func b)
 78{
 79    if(a.up*b.down<b.up*a.down) return a;
 80    else return b;
 81}

 82func solve()
 83{
 84    for(int i=0;i<de;i++)
 85        num[i]=func(data[i]);
 86    int down=aver.up/aver.down,up=aver.up%aver.down?aver.up/aver.down+1:aver.up/aver.down;
 87    for(int i=0;i<de;i++)
 88        if(data[i]<=down) dp[0][i]=aver-num[i];
 89        else dp[0][i]=num[i]-aver;
 90    for(int i=1;i<k;i++)
 91    {
 92        for(int j=0;j<de;j++)
 93            dp[i][j]=dp[i-1][j]+aver;
 94        int last=-1;
 95        func ans=func(0xfffffff);
 96        for(int j=0;j<de;j++)
 97        {
 98            while(data[j]-data[last+1]>=up)
 99            {
100                last++;
101                if(!last) ans=     dp[i-1][last]-num[last]-aver;
102                else ans=min(ans,dp[i-1][last]-num[last]-aver);
103            }

104            if(last!=-1)
105                dp[i][j]=min(dp[i][j],ans+num[j]);
106            
107        }

108        int s=-1,e=0;
109        q[0]=0;
110        for(int j=1;j<de;j++)
111        {
112            //add
113            while(s!=e&&dp[i-1][j]+num[j]<=dp[i-1][q[e]]+num[q[e]])
114                 e--;
115            q[++e]=j;
116            //erase
117            while(s!=e&&data[j]-data[q[s+1]]>down) s++;
118            if(s!=e)
119                dp[i][j]=min(dp[i][j],dp[i-1][q[s+1]]+aver-num[j]+num[q[s+1]]);
120
121        }

122    }

123    return dp[k-1][de-1];
124
125}

126int main()
127{
128    //freopen("land.in","r",stdin);
129    //freopen("ans.txt","w",stdout);
130    pair<int,int> d[100000];
131    map<int,int> refer;
132    int n,test=1;
133    while(scanf("%d%d",&n,&k)!=EOF&&(n||k))
134    {
135        refer.clear();
136        aver.up=n;
137        aver.down=k;
138        aver.simple();
139        for(int i=0;i<n;i++)
140            scanf("%d%d",&d[i].first,&d[i].second);
141        for(int i=0;i<n;i++)
142            refer[d[i].first]++;
143        data[0]=0;
144        de=1;
145        for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
146            data[de++]=(i->second);        
147        for(int i=1;i<de;i++)
148            data[i]+=data[i-1];
149    
150        func ans=solve();
151        refer.clear();
152        for(int i=0;i<n;i++)
153            refer[d[i].second]++;
154        data[0]=0;
155        de=1;
156        for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
157            data[de++]=(i->second);        
158        for(int i=1;i<de;i++)
159            data[i]+=data[i-1];
160        ans=min(ans,solve());
161        ans.down*=k;
162        ans.simple();
163        printf("%d. %d/%d\n",test++,ans.up,ans.down);
164    }

165    return 0;
166}


posted on 2011-10-18 02:17 yzhw 阅读(356) 评论(1)  编辑 收藏 引用 所属分类: DP

评论

# re: pku 3998 Land Division DP斜率优化 2012-05-23 01:55 lzqxh

这个题卡常数。。你还用分数类。=。=
把每个点的权值设为m,则每部分平均权值为n。之后转为整数操作
之后,我离散化点Tle了。证明大数据比较多,离散化优势在于处理小数据,但是大数据复杂度退化成O(nlogn)。。
之后改成原坐标直接作为dp状态。。400+msAc了
最后:好像是贪心+单调队列。。没有发现用到斜率的地方啊  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜