cf1060E. Sergey and Subway(思維 枚舉)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/12/06/10079774.html
-Advertisement-
Play Games

題意 "題目鏈接" Sol 好好讀題 = 送分題 不好好讀題 = 送命題 開始想了$30$min數據結構發現根本不會做,重新讀了一遍題發現是個傻逼題。。。 $C_{i, j} = a[i] b[j]$ 根據乘法分配律,題目就變成了在數組$a, b$中分別選一段連續的區間,要求權值和相乘$ defin ...


題意

題目鏈接

Sol

好好讀題 => 送分題

不好好讀題 => 送命題

開始想了\(30\)min數據結構發現根本不會做,重新讀了一遍題發現是個傻逼題。。。

\(C_{i, j} = a[i] * b[j]\)

根據乘法分配律,題目就變成了在數組\(a, b\)中分別選一段連續的區間,要求權值和相乘\(<= X\),最大化區間長度乘積

\(n^2\)模擬一下即可

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long 
#define LL long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
#define chmin(x, y) (x = x < y ? x : y)
using namespace std;
const int MAXN = 2001, INF = 1e18 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int N, M, a[MAXN], b[MAXN], f[MAXN], g[MAXN], Lim, ans;
main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= M; i++) b[i] = read();
    memset(f, 0x7f, sizeof(f));
    memset(g, 0x7f, sizeof(g));
    Lim = read();
    for(int i = 1; i <= N; i++) {
        int mn = 0;
        for(int j = i; j <= N; j++) mn += a[j], chmin(f[j - i + 1], mn);
    }
    for(int i = 1; i <= M; i++) {
        int mn = 0;
        for(int j = i; j <= M; j++) mn += b[j], chmin(g[j - i + 1], mn);
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(f[i] * g[j] <= Lim)
                ans = max(ans, j * i);
        }
    }
    cout << ans;
    return 0;   
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 題目內容: 電腦內部用二進位來表達所有的值。一個十進位的數字,比如18,在一個32位的電腦內部被表達為00000000000000000000000000011000。可以看到,從左邊數過來,在第一個1之前,有27個0。我們把這些0稱作前導的零。 現在,你的任務是寫一個程式,輸入一個整數,輸出在 ...
  • 在Timer模塊中有提到,libuv控制著延遲事件的觸發,那麼必須想辦法精確控制時間。 如果是JS,獲取當前時間可以直接通過Date.now()得到一個時間戳,然後將兩段時間戳相減得到時間差。一般情況下當然沒有問題,但是這個方法並不保險,因為本地電腦時間可以修改。 libuv顯然不會用這麼愚蠢的辦 ...
  • 題目內容: 一個正整數的因數是所有可以整除它的正整數。而一個數如果恰好等於除它本身外的因數之和,這個數就稱為完數。例如6=1+2+3(6的因數是1,2,3)。 現在,你要寫一個程式,讀入兩個正整數n和m(1<=n<m<1000),輸出[n,m]範圍內所有的完數。 提示:可以寫一個函數來判斷某個數是否 ...
  • 題目內容: 每個非素數(合數)都可以寫成幾個素數(也可稱為質數)相乘的形式,這幾個素數就都叫做這個合數的質因數。比如,6可以被分解為2x3,而24可以被分解為2x2x2x3。 現在,你的程式要讀入一個[2,100000]範圍內的整數,然後輸出它的質因數分解式;當讀到的就是素數時,輸出它本身。 輸入格 ...
  • json數據格式 參見 "json數據格式說明" 。 如果沒操作過json數據,建議先看下上面的文章,有助於理解本文後面的內容。 Go json包 Marshal():Go數據對象 json數據 UnMarshal():Json數據 Go數據對象 構建json數據 Marshal()和Marshal ...
  • 在監控設備的時候,在server端的日誌中有時候會見到類似another network error, wait for 15s seconds的異常,今天我們看下這個問題的出現原因和解決方案:問題定位到poller.c,看下下麵兩份代碼:這個get_values的部分代碼: 這裡是zbx_deac ...
  • yield 關鍵字 yield 是在:PEP 255 -- Simple Generators 這個pep引入的 yield 只能在函數內部使用,包含yield語句的函數稱為生成器函數 當調用生成器函數時,並不會執行函數體中的代碼,而是返回一個生成器對象 每次調用生成器對象的next()方法時,才會 ...
  • 我們都見識過requests庫在靜態網頁的爬取上展現的威力,我們日常見得最多的為get和post請求,他們最大的區別在於安全性上: 1、GET是通過URL方式請求,可以直接看到,明文傳輸。 2、POST是通過請求header請求,可以開發者工具或者抓包可以看到,同樣也是明文的。 3.GET請求會保存 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...