正文

bzoj1933[shoi2007]bookcase书柜的尺寸

Achen  Achen  2022-09-21  543

关键词：

神奇的dp优化。

考虑6维状态的dp,分别表示三行高和宽，显然MLE&&TLE。

把高排个序，从大到小往架上放，那么若不是重开一行便对高度没有影响。

然后求出宽度的sum,dp[i][j]表示第一行放了i的宽度，二行放了j的宽度，三行放了sum-i-j宽度的最小的高度值。

先把所有书放在第三行，然后从第二本开始转移，考虑往其他行移的情况。

避免MLE要滚动数组。

注意最后更新答案时保证i>0&&j>0&&sum-i-j>0且dp[i][j]!=INF;

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
typedef long long LL;
using namespace std;
int n,sum,f[2][2150][2150],ans=1e9;
struct book {
    int hi,ti;
    friend bool operator <(const book &A,const book &B) {
        return A.hi>B.hi;
    }
}bk[75];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
        scanf("%d%d",&bk[i].hi,&bk[i].ti);
    sort(bk+1,bk+n+1);
    for(int i=1;i<=n;i++) sum+=bk[i].ti;
    int o=0;
    memset(f,127/3,sizeof(f));
    f[0][0][0]=bk[1].hi;
    for(int i=2;i<=n;i++) {
        o^=1;
        for(int j=0;j<=sum;j++) {
            for(int k=0;k<=sum&&j+k<sum;k++) {
                f[o][j][k]=min(f[o][j][k],f[o^1][j][k]);
                if(!j) f[o][j+bk[i].ti][k]=min(f[o][j+bk[i].ti][k],f[o^1][j][k]+bk[i].hi);
                else f[o][j+bk[i].ti][k]=min(f[o][j+bk[i].ti][k],f[o^1][j][k]);
                if(!k) f[o][j][k+bk[i].ti]=min(f[o][j][k+bk[i].ti],f[o^1][j][k]+bk[i].hi);
                else f[o][j][k+bk[i].ti]=min(f[o][j][k+bk[i].ti],f[o^1][j][k]);
                if(i==n&&j!=0&&k!=0&&f[o][j][k]!=707406378) {
                    ans=min(ans,f[o][j][k]*max(max(j,k),sum-j-k));
                }
            }
        }
    }
    printf("%d
",ans);
    return 0;
}

View Code

bzoj1933[shoi2007]bookcase书柜的尺寸

神奇的dp优化。考虑6维状态的dp,分别表示三行高和宽，显然MLE&&TLE。把高排个序，从大到小往架上放，那么若不是重开一行便对高度没有影响。然后求出宽度的sum,dp[i][j]表示第一行放了i的宽度，二行放了j的宽度，三行放了... 查看详情

bzoj1934:[shoi2007]vote善意的投票

二次联通门: BZOJ1934:[Shoi2007]Vote善意的投票 /*BZOJ1934:[Shoi2007]Vote善意的投票最小割*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgcharc=getc 查看详情

bzoj13821935:[shoi2007]tree园丁的烦恼

1935:[Shoi2007]Tree园丁的烦恼TimeLimit: 15Sec MemoryLimit: 357MBSubmit: 1261 Solved: 578[Submit][Status][Discuss]Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园查看详情

bzoj1934:[shoi2007]vote善意的投票

题目链接bzoj1934:[Shoi2007]Vote善意的投票题解睡觉作为源点，不睡作为汇点对于一个人违背自己的意愿，连向与自己意愿相反的源汇，容量为1对于朋友意见相反，在朋友之间连容量为2的双向边，切得时候双向边使得该边漫流求一... 查看详情

bzoj1934:[shoi2007]vote善意的投票

1934:[Shoi2007]Vote善意的投票TimeLimit:1Sec MemoryLimit:64MBSubmit:2489 Solved:1544[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让... 查看详情

bzoj1935[shoi2007]tree园丁的烦恼(代码片段)

(verb|bzoj1935[SHOI2007]Tree园丁的烦恼|)静态询问平面点数(x_i,y_iin[0,10^7],,mleq5 imes10^5)二维偏序，cdq分治可以直接cdq分治，也可以离散化后用BIT做、、注意排序时若(x,y)相同，要将点放在询问前面时间复杂度(O(nlogn))代码cdq分治#include<b... 查看详情

bzoj-1934:[shoi2007]vote善意的投票(网络流最小割)

1934:[Shoi2007]Vote善意的投票TimeLimit: 1Sec MemoryLimit: 64MBSubmit: 2353 Solved: 1470[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对查看详情

bzoj千题计划143：bzoj1935:[shoi2007]tree园丁的烦恼

http://www.lydsy.com/JudgeOnline/problem.php?id=1935 二维偏序问题排序x，离散化树状数组维护y #include<cstdio>#include<iostream>#include<algorithm>#definelowbit(x)x&-xusingnamespacestd;#de 查看详情

[bzoj1935][shoi2007]tree园丁的烦恼_树状数组

Tree园丁的烦恼bzoj-1935Shoi-2007题目大意：给定平面上的$n$个点，$m$次查询矩形点个数。注释：$1len,mle5cdot10^5$。想法：静态二维数点。$OrzWinniechen$，真tm敢写$KD-Tree$，虽然$T$了..正常这种静态的二维数点我们都要请到树状数组。最简... 查看详情

bzoj-1934:[shoi2007]vote善意的投票(网络流最小割)

1934:[Shoi2007]Vote善意的投票TimeLimit: 1Sec MemoryLimit: 64MBSubmit: 2353 Solved: 1470[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重查看详情

bzoj1935:[shoi2007]tree园丁的烦恼

1935:[Shoi2007]Tree园丁的烦恼Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁... 查看详情

bzoj1934:[shoi2007]vote善意的投票

最大流。。建图方式都是玄学啊。。//Dinic是O(n2m)的。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>usingnamespacestd;#definerep(i,s,t)for(inti=s;i<=t;i++)#definedwn(i,s,t)f 查看详情

bzoj1934:[shoi2007]vote善意的投票

get到新姿势，最小割=最大流，来个大佬的PPT这道题的做法是将st和1的xpy连，0的xpy和ed连，xpy之间jy连双向边，然后呢答案就是最小割。#include<cstdio>#include<iostream>#include<cstring>usingnamespacestd;structnode{intx,y,c,next,other;}a[11... 查看详情

bzoj1934[shoi2007]vote善意的投票

我大概是把自己水废掉了。第一眼匈牙利？不知道怎么想到的，然后发现不可做。似乎是网络流呀。看了半天硬是没把图建出来。出去冷静一下。wc这不是和文理分科那啥一模一样嘛，还简单得多。。。我是zz，鉴定完毕。//Twenty... 查看详情

bzoj1934[shoi2007]vote善意的投票（最小割）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1934 【题目大意】　　每个人对于投票都有自己原来的观点：1或者0，　　他可以违背自己原来的意愿投相反的票，　　同时存在一些相互的朋友关系，　　我们定义... 查看详情

bzoj1935:[shoi2007]tree园丁的烦恼(代码片段)

这题本来是想用二维树状数组水的。然后不会动态开数组，所以顺便补了一发cdq。第一维时间，第二维x，第三维y，（其实我自己的感觉是第一维可以不要的），xy很大so离散化谢谢。询问拆成4个。大家都懂。#include<cstdio>#inc... 查看详情

bzoj1934：[shoi2007]善意的投票&bzoj2768：[jloi2010]冠军调查——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=1934https://www.lydsy.com/JudgeOnline/problem.php?id=2768幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的... 查看详情

bzoj.1935.[shoi2007]tree园丁的烦恼(cdq分治三维偏序)

题目链接矩形查询可以拆成四个点的前缀和查询(树套树显然但是空间不够)每个操作表示为(t,x,y)，t默认有序，对x分治，y用树状数组维护初始赋值需要靠修改操作实现。//119964kb4380ms#include<cstdio>#include<cctype>#include<algori... 查看详情