洛谷 P1736 創意吃魚法(多維DP)

題目描述

回到家中的貓貓把三桶魚全部轉移到了她那長方形大池子中,然后開始思考:到底要以何種方法吃魚呢(貓貓就是這么可愛,吃魚也要想好吃法 ^_*)。她發現,把大池子視為01矩陣(0表示對應位置無魚,1表示對應位置有魚)有助于決定吃魚策略。

在代表池子的01矩陣中,有很多的正方形子矩陣,如果某個正方形子矩陣的某條對角線上都有魚,且此正方形子矩陣的其他地方無魚,貓貓就可以從這個正方形子矩陣“對角線的一端”下口,只一吸,就能把對角線上的那一隊鮮魚吸入口中。

貓貓是個貪婪的家伙,所以她想一口吃掉盡量多的魚。請你幫貓貓計算一下,她一口下去,最多可以吃掉多少條魚?

輸入輸出格式

輸入格式:

有多組輸入數據,每組數據:

第一行有兩個整數n和m(n,m≥1),描述池塘規模。接下來的n行,每行有m個數字(非“0”即“1”)。每兩個數字之間用空格隔開。

對于30%的數據,有n,m≤100

對于60%的數據,有n,m≤1000

對于100%的數據,有n,m≤2500

輸出格式:

只有一個整數——貓貓一口下去可以吃掉的魚的數量,占一行,行末有回車。

--------------------------------------------我是分割線------------------------------------------------

這題我用的是N2logN的二分,還挺好寫的,效率也很可觀。

進入正題:

首先要對角線要分成兩種,一種是/這樣的,一種是\這樣的(靈魂題解~~),這是兩個相似的問題,我們可以先解決一個,然后把代碼復制一下(嘿嘿嘿)。

我們來看一下\這樣的對角線,式子很明顯:

f[i][j]表示以(i,j)為終點的對角線長度,因此這里一定有要魚

如果矩陣(i-x,j-x,i,j)是滿足題目要求的,那么f[i][j]=max(f[i][j],x)。

同時我們發現,1.x越大越好。2.x的上界是f[i-1][j-1],因為超過這個一定不滿足要求。3.如果x不滿足要求,那么x到其上界就都不滿足。

似乎滿足單調性?

那么我們可以二分x。

之后我們再來看滿足題目要求的矩陣

舉個例子:

1 0 0 0

0 1 0 1

0 0 1 0

0 0 0 1

當i=4,j=4時,由于我們之前算出來f[3][3]是三,那么矩陣(1,1,3,3)一定是符合要求的,所以我們只需要判斷第i行1到j個元素與第j行1到i個元素有沒有魚就可以了。

但如果暴力算的話會T,我們可以算矩陣(i-x,j-x,i,j)的和是不是x+1。于是就可以用到我們的二維前綴和了。

貼一下代碼:

?

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int f[2501][2501],s[2501][2501],i;
int a[2501][2501],n,m,l,r,mid,ans,j;
inline int read(){int x=0,p=1; char ch=getchar();while (ch<'0'||ch>'9') {if (ch == '-') p=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}return x*p;
}
int main(){n=read(); m=read();for (i=1; i<=n; i++)for (j=1; j<=m; j++){a[i][j]=read();s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}for (i=1; i<=n; i++)for (j=1; j<=m; j++){if (a[i][j]){f[i][j]=1;if (f[i-1][j-1]){l=0; r=f[i-1][j-1];while (l<=r){mid=l+r>>1;if (s[i][j]-s[i-mid-1][j]-s[i][j-mid-1]+s[i-mid-1][j-mid-1]==mid+1)l=mid+1;else r=mid-1;}f[i][j]=max(f[i][j],l);}}ans=max(ans,f[i][j]);}memset(f,0,sizeof(f));for (i=1; i<=n; i++)for (j=m; j>=1; j--){if (a[i][j]){f[i][j]=1;l=0; r=f[i-1][j+1];while (l<=r){mid=l+r>>1;if (s[i][j+mid]-s[i][j-1]-s[i-mid-1][j+mid]+s[i-mid-1][j-1]==mid+1)l=mid+1;else r=mid-1;}f[i][j]=max(f[i][j],l);}ans=max(ans,f[i][j]);}printf("%d",ans);return 0;
}

?

轉載于:https://www.cnblogs.com/taduro/p/9466107.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/279631.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/279631.shtml
英文地址,請注明出處:http://en.pswp.cn/news/279631.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

計算機組裝和維護_如何構建自己的計算機,第二部分:組裝在一起

計算機組裝和維護So you’ve selected your parts, double- and triple-checked their compatibility, and waited for economy shipping to bring them all to your door. It’s time to get to the fun part: putting them all together. 因此&#xff0c;您已經選擇了零件&a…

Python學習-集合的常見用法

st [1,2,3,4,5] ct [2,3,4,5,76] list set(["name", list, try]) list2 set(["name", list, try, but, test]) # 兩個列表去重&#xff0c;利用集合st set(st) #設為集合 ct set(ct) print(st, type(st))sct0 st.union(ct) #并集 sct st | ct …

Autofac之自動裝配

從容器中的可用服務中選擇一個構造函數來創造對象&#xff0c;這個過程叫做自動裝配。這個過程是通過反射實現的 默認 思考這么一個問題,如果注冊類型中存在多個構造函數,那么Autofac會選擇哪一個來創建類型的實例 答案是"盡可能最多參數" class ConstructorClass {p…

對Emlog 6.0 Beta的完整代碼審計過程

Emlog 6.0 beta版本&#xff0c;這可能是最后一篇關于PHP語言CMS的代碼審計文章&#xff0c;此次將詳細記錄完整的審計過程。 文章基本上完整記錄小東的對此CMS審計過程&#xff0c;或許顯得繁瑣&#xff0c;但代碼審計的過程就是這樣&#xff0c;發現可能項&#xff0c;然后精…

SINOCES 2011

突然發現又好久沒寫過日志了 是在是太懶了… 難得休假去看了眼消費電子 感覺實在是一年不如一年 佳能、索尼不見蹤影&#xff0c;相機滿場沒見一家&#xff08;大牌子是真沒見到&#xff09; 華碩技嘉微星等主板廠商同樣失蹤… PC方面&#xff0c;聯想貌似是來賣電腦包鼠標的&a…

esim卡與ms卡的區別_什么是eSIM,它與SIM卡有何不同?

esim卡與ms卡的區別With the launch of the Apple Watch 3, the term “eSIM” has been thrown around a lot. And now, Google’s Pixel 2 is the first phone to use this new technology, it’s time we take a closer look at what it is, what it does, and what this me…

機器學習實戰之logistic回歸分類

利用logistic回歸進行分類的主要思想&#xff1a;根據現有數據對分類邊界建立回歸公式&#xff0c;并以此進行分類。 logistic優缺點&#xff1a; 優點&#xff1a;計算代價不高&#xff0c;易于理解和實現。缺點&#xff1a;容易欠擬合&#xff0c;分類精度可能不高。 .適用數…

HDU 6343.Problem L. Graph Theory Homework-數學 (2018 Multi-University Training Contest 4 1012)

6343.Problem L. Graph Theory Homework 官方題解: 一篇寫的很好的博客: HDU 6343 - Problem L. Graph Theory Homework - [(偽裝成圖論題的)簡單數學題] 代碼: 1 //1012-6343-數學2 #include<iostream>3 #include<cstdio>4 #include<cstring>5 #include<…

Android GridView LruCache

照片墻這種功能現在應該算是挺常見了&#xff0c;在很多應用中你都可以經常看到照片墻的身影。它的設計思路其實也非常簡單&#xff0c;用一個GridView控件當作“墻”&#xff0c;然后隨著GridView的滾動將一張張照片貼在“墻”上&#xff0c;這些照片可以是手機本地中存儲的&a…

如何在Android TV上自定義推薦行

When you fire up Android TV, the first thing you see is a list of movies and shows the system thinks you’ll like. It’s often full of the latest flicks or hottest news, but sometimes it could just be things relevant to your interests and the apps you have…

遞歸 段錯誤 習題

段錯誤 遞歸里面算階乘 f(10000000)沒有輸出&#xff0c;使用gdb 顯示 SIGSEGV--段錯誤編譯后產生的可執行文件里面保存著什么&#xff1f;UNIX/Linux 用 ELFDOS下用COFFWindows用PE&#xff08;COFF擴充而得&#xff09;段&#xff08;segmentation&#xff09;二進制文件內的…

你知道你常用的dos和linux命令嗎?

功能 Linux MS-DOS 進入到該目錄 cd cd 列舉文件 ls dir 創建目錄 mkdir mkdir 清除屏幕 clear cls 復制文件 cp copy 移動文件 mv move 刪除文件 rm del 查看文件 less more 文件重命名 mv ren 比較文件內容 diff fc 查看當前路徑 pwd chd…

steam串流到手機_如何從手機將Steam游戲下載到PC

steam串流到手機Steam allows you to remotely install games from your smartphone, just like you can with a PlayStation 4 or Xbox One. You can download games to your gaming PC from anywhere, ensuring those big downloads are complete and the game is ready to p…

編寫安裝配置ftp-samba服務腳本

本腳本實例的要求如下&#xff1a; 1、公司有公共共享目錄public,所有員工均可讀寫&#xff0c;但不允許刪除其他員工的文件;不能匿名登錄 2、每部門均有共享目錄&#xff0c;部門經理可讀寫&#xff0c;部門員工可讀&#xff1b; 非本部門員工不能訪問&#xff08;caiwu、rens…

利用java實現excel轉pdf文件

在有些需求當中我們需要抓取字段并且填充到excel表格里面&#xff0c;最后將excel表格轉換成pdf格式進行輸出&#xff0c;我第一次接觸這個需求時&#xff0c;碰到幾個比較棘手的問題&#xff0c;現在一一列出并且提供解決方案。 1&#xff1a;excel轉pdf出現亂碼&#xff1a; …

Jmeter HTTP請求后響應數據顯示亂碼解決方法

Jmeter請求后結果樹里無論是text還是html響應數據顯示亂碼&#xff0c;這是因為jmeter 編碼格式配置文件默認不開啟導致的&#xff0c;解決方法如下&#xff1a; 1&#xff09;進入jmeter-***\bin目錄下&#xff0c;找到jmeter.properties文件&#xff0c;以文本文件形式打開 2…

禁用windows10更新_如何在Windows 10中禁用投影

禁用windows10更新The drop shadows on applications in the Windows 10 preview are really big and suspiciously similar to the ones in OS X, and if they aren’t your speed, you can easily remove them. We actually think they look good, but since somebody out th…

如何訪問 Service?- 每天5分鐘玩轉 Docker 容器技術(99)

前面我們已經學習了如何部署 service&#xff0c;也驗證了 swarm 的 failover 特性。不過截止到現在&#xff0c;有一個重要問題還沒有涉及&#xff1a;如何訪問 service&#xff1f;這就是本節要討論的問題。 為了便于分析&#xff0c;我們重新部署 web_server。 ① docker se…

sqlyog下載

sqlyog下載&#xff08;附注冊碼&#xff09;&#xff1a;http://www.onlinedown.net/soft/24926.htm轉載于:https://www.cnblogs.com/shujuxiong/p/9474496.html

Linux配置手冊(二)配置DHCP服務器

1.檢查是否安裝DHCP服務器軟件 2.掛在RHEL5系統光盤 3.安裝DHCP服務軟件 4.將模板配置文件復制并覆蓋現在的配置文件 5.配置修改dhcpd.conf文件 配置信息 默認租約時間 default-lease-time 最大租約時間 max-lease-time 局域網內所有主機的域名 option domain-name 客戶機所使用…