正文

[poi2006]ork-ploughing

faced  faced  2022-10-19  615

关键词：

[POI2006]ORK-Ploughinghttps://www.luogu.org/problemnew/show/P3444

题目描述

(Byteasar) 想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行), 在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为 (1),耕地的长宽分别为 (m) 和 (n),不幸的是 (Byteasar) 只有一匹老弱的马,从马开始耕地开始,只有当它耕完了一边才会停下休息。但有些地会非常难耕以至于马会非常的累,因此 (Byteasar) 需要特别小心。当耕完了一边之后,马可以停下来休息恢复体力。每块地耕种的难度不一,但是 (Byteasar) 都非常清楚。我们将地分成 (m*n) 块单位矩形 ——我们用坐标((I,j))来定义它们。每块地都有一个整数 (T[I,J]),来定义((I,j))的耕种难度。所以每次马耕一边地时的难度就是所有它耕种的地的难度总和,对于这匹虚弱的马而言,这个值不能超过他的体力值。(Byteasar) 想知道在马不死掉的情况下最少需要耕多少次才能把地耕完。

输入格式：

第一行三个整数, (K,M,N)。 (1<=k<=200 000 000),(1<=m,n<=2000).其中 (K) 表示马的体力值。接下来 (N) 行每行 (M) 个整数表示难度值。((0<=)难度值(<=10 000))

输出格式：

一个整数表示最少的耕种次数(保证马能耕完)。

输入样例：

12 6 4
6 0 4 8 0 5
0 4 5 4 6 0
0 5 6 5 6 0
5 4 0 0 5 4

输出样例：

贪心:
最少次数:(min(n,m)):直接只横切或只纵切切完
最多次数:(n+m):既横切又纵切
贪心策略:先优先横切,枚举切左边的次数([1,m]),尽可能少切右边
再优先纵切,枚举切上面的次数([1,n]),尽可能少切下边
所有次数取(min)即可

前缀和优化查询O(1)
存在无解的情况返回inf

#define RG register
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2005;
inline int read()
{
    RG int x=0,w=1;RG char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
    return x*w;
}
int k,m,n,Ans=1e9;
int a[N][N],r[N][N],l[N][N];
inline int del1(int lim,int L,int R,int U,int D)
{
    int Sum=0;
    while(L<=R&&U<=D)
    {
        Sum++;
        if(l[D][L]-l[U-1][L]<=k){L++;continue;}
        if(l[D][R]-l[U-1][R]<=k){R--;continue;}
        if((r[U][R]-r[U][L-1]<=k)&&(U<=lim)){U++;continue;}
        if(r[D][R]-r[D][L-1]<=k)D--;
        else return 1e9;
    }
    return Sum;
}
inline int del2(int lim,int L,int R,int U,int D)
{
    int Sum=0;
    while(L<=R&&U<=D)
    {
        Sum++;
        if(r[U][R]-r[U][L-1]<=k){U++;continue;}
        if(r[D][R]-r[D][L-1]<=k){D--;continue;}
        if((l[D][L]-l[U-1][L]<=k)&&(L<=lim)){L++;continue;}
        if(l[D][R]-l[U-1][R]<=k)R--;
        else return 1e9;
    }
    return Sum;
}
int main()
{
    k=read();
    m=read();
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            a[i][j]=read();
            r[i][j]=r[i][j-1]+a[i][j];
            l[i][j]=l[i-1][j]+a[i][j];
        }
    for(int i=0;i<n;i++)Ans=min(Ans,del1(i,1,m,1,n));
    for(int i=0;i<m;i++)Ans=min(Ans,del2(i,1,m,1,n));
    printf("%d
",Ans);
    return 0;
}

bzoj1520poi2006szk-schools

1520:[POI2006]Szk-SchoolsTimeLimit: 5Sec MemoryLimit: 64MBSubmit: 771 Solved: 398[Submit][Status][Discuss]DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleIn 查看详情

bzoj1520[poi2006]szk-schoolskm算法

【BZOJ1520】[POI2006]Szk-SchoolsDescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。#include<cstdio>#inclu... 查看详情

[poi2006]okr-periodsofwords(代码片段)

---恢复内容开始---题目描述Astringisafinitesequenceoflower-case(non-capital)lettersoftheEnglishalphabet.Particularly,itmaybeanemptysequence,i.e.asequenceof0letters.ByA=BCwedenotesthatAisastringobtainedbyconcaten 查看详情

1511:[poi2006]okr-periodsofwords(代码片段)

1511:[POI2006]OKR-PeriodsofWordshttps://www.lydsy.com/JudgeOnline/problem.php?id=1511 题意：　　对于一个串的所有前缀，设为s，求出它的最大前缀Q，使得s为QQ的前缀。求最大前缀长度的和。分析：　　KMP+next数组。　　next数组表示的是这个字... 查看详情

[bzoj1510][poi2006]kra-thedisks_暴力

Kra-TheDisksbzoj-1510POI-2006题目大意：题目链接。注释：略。想法：不难发现其实只有前缀最小值是有效的。进而我们把盘子一个一个往里放，弄一个自底向上的指针往上蹦即可。时间复杂度$O(n)$。Code：#include<iostream>#include<cst... 查看详情

bzoj1510[poi2006]kra-thedisks*

bzoj1510[POI2006]Kra-TheDisks题意：一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。题解：首先利... 查看详情

p3435[poi2006]okr-periodsofwords(代码片段)

P3435[POI2006]OKR-PeriodsofWords题解传送门kmp注意：由于题目说只要A满足是2Q的前缀，所以求的不是严格的最大循环子串（20pts）我们需要求出的是在主串中最小的，既是前缀又是后缀的子串利用f数组的性质：前缀i的长度为next[i]的前... 查看详情

[bzoj1513][poi2006]tet-tetris3d

[BZOJ1513][POI2006]Tet-Tetris3D试题描述Task:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使... 查看详情

p3440[poi2006]szk-schools（费用流）(代码片段)

P3440[POI2006]SZK-Schools每所学校$i$开一个点，$link(S,i,1,0)$每个编号$j$开一个点，$link(i,T,1,0)$蓝后学校向编号连边，$link(i,j,1,val)$最后跑一遍费用流如果没有满流就是$NIE$否则就是最小代价了#include<iostream>#include<cstdio>#include<... 查看详情

luogu3444ork-ploughing（贪心）

【Luogu3444】ORK-Ploughing（贪心）题面Luogu题解我们知道，如果我们选定了以横向为主，或者纵向为主，那么就有尽可能减少另一个方向上耕地的次数所以分开贪心，但是本质相同，所以接下来只考虑纵向为主既然确定了以纵向为主... 查看详情

bzoj1513:[poi2006]tet-tetris3d

Description三维空间从上落下几个长方体,问最后的最高高度.Solution二维线段树.感觉这种东西是可以yy出来的吧..对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.开4倍内存会MLE...Co... 查看详情

[poi2006]okr-periodsofwords(代码片段)

DescriptionLuogu3435对一个字符串(A)，定义其周期(Q)为，(Q)为(A)的前缀（(Q!=A)）且(A)为(QQ)的前缀（(A)可以等于(QQ)）。求一个字符串的所有前缀的最长周期的长度之和。Solution首先观察周期的定义，可以发现，一旦该字符串有一个前缀... 查看详情

bzoj1513[poi2006]tet-tetris3d二维线段树

【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情

解题：poi2006pro-professorszu(代码片段)

题面这个题是比较套路的做法啦，建反图后缩点+拓扑排序嘛，对于所有处在$size>=2$的SCC中的点都是无限解(可以一直绕)然后注意统计的时候的小细节，因为无限解/大解也要输出，所以我们把这些点统一统计成36501，然后所有的... 查看详情

bzoj1511:[poi2006]okr-periodsofwordskmp(代码片段)

n-ne[n]是n的最长循环节长度，其实就是n-最短前缀=后缀长度然后我们要求最短循环节，其实就是ne一直往前跳，跳到不能跳为止，这时的n-ne[n]就是n的最短循环节长度#include<iostream>#include<cstdio>usingnamespacestd;constintN=1000005;in... 查看详情

bzoj1513[poi2006]tet-tetris3d(代码片段)

二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情

luogu3435poi2006okr-periodsofwords（kmp）(代码片段)

　　显然答案应该是Σi-next[next[……next[i]]](next[next[……next[i]]]>0)。递推即可。#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#include<algorith 查看详情

bzoj1520[poi2006]szk-schools费用流

题目描述输入输出如果有可行解,输出最小代价,否则输出NIE.样例输入5112311513255415103331样例输出9题解费用流设xi表示学生，yi表示编号，那么S->xi，容量为1，费用为0；xi->能够使得xi接受的yj，容量为1，费用为按照题目中计算... 查看详情