首頁 web前端 html教學 RCC 2014 Warmup (Div. 2)Cunning Gena_html/css_WEB-ITnose

RCC 2014 Warmup (Div. 2)Cunning Gena_html/css_WEB-ITnose

Jun 24, 2016 pm 12:05 PM

题目链接

  • 题意:
    输入n:人数,m:题目数,b:每个显示器价格
    然后对于每个人,输入x:需要的钱,k至少需要的显示器个数,m:会的题目
    下一行输入会的题目
    选一些人,使得包括所有的题目且钱最少(每个人需要的钱加上显示器的钱)
    (1?≤?n?≤?100; 1?≤?m?≤?20; 1?≤?b?≤?109)、 (1?≤?xi?≤?109; 1?≤?ki?≤?109; 1?≤?mi?≤?m)
  • 分析:
    如果题目中的数据量比较小,显然是可以用状压DP来做的,就是加一个当前用的显示器的状态即可。但是关键在于,题目中的k是比较大的,所以如果把这一维加上去显然是不能进行DP的。那么我们可以尝试着进行转化,既然基本符合DP的原则,只有显示器数量这一个状态是不符合的,那么就考虑一下如何处理这一个状态。这个状态要求是至少,那么我们如果考虑某一时刻所选择的所有人的k的最大值时,其他的那些人是不用考虑k值的,因为最后一个的k是最大的。那么就有方向了,可以将所有的人安装k排序,对于0 - i-1的人是正常的DP(不考虑k,只考虑题目),到第i个人时,找一下那些状态可以和i人的题目加起来达到所有值(覆盖所有题目),不过这时候加上k*percost即可。
    再说一下,这个问题其实也可以考虑成DLX,每一个人作为行,题目作为列。但是问题在于,既要最小费用又要计算k,还是一个重复覆盖,剪枝效率不高,对于这个数据量会超时,不过也是一个方向。
  • 重点:
    关键在于对于大的一个维度的处理,使得问题可以用状压DP来解
    注意对INF的初始化
  • const LL INF = 1100000000000000000;const int MAXN = 110;struct Node{    int cost, Min, n;    int operator   <br>   <br>   
    登入後複製
    本網站聲明
    本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

    熱AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智慧驅動的應用程序,用於創建逼真的裸體照片

    AI Clothes Remover

    AI Clothes Remover

    用於從照片中去除衣服的線上人工智慧工具。

    Undress AI Tool

    Undress AI Tool

    免費脫衣圖片

    Clothoff.io

    Clothoff.io

    AI脫衣器

    Video Face Swap

    Video Face Swap

    使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

    熱工具

    記事本++7.3.1

    記事本++7.3.1

    好用且免費的程式碼編輯器

    SublimeText3漢化版

    SublimeText3漢化版

    中文版,非常好用

    禪工作室 13.0.1

    禪工作室 13.0.1

    強大的PHP整合開發環境

    Dreamweaver CS6

    Dreamweaver CS6

    視覺化網頁開發工具

    SublimeText3 Mac版

    SublimeText3 Mac版

    神級程式碼編輯軟體(SublimeText3)

    熱門話題

    Java教學
    1655
    14
    CakePHP 教程
    1413
    52
    Laravel 教程
    1306
    25
    PHP教程
    1252
    29
    C# 教程
    1226
    24
    HTML容易為初學者學習嗎? HTML容易為初學者學習嗎? Apr 07, 2025 am 12:11 AM

    HTML適合初學者學習,因為它簡單易學且能快速看到成果。 1)HTML的學習曲線平緩,易於上手。 2)只需掌握基本標籤即可開始創建網頁。 3)靈活性高,可與CSS和JavaScript結合使用。 4)豐富的學習資源和現代工具支持學習過程。

    了解HTML,CSS和JavaScript:初學者指南 了解HTML,CSS和JavaScript:初學者指南 Apr 12, 2025 am 12:02 AM

    WebDevelovermentReliesonHtml,CSS和JavaScript:1)HTMLStructuresContent,2)CSSStyleSIT和3)JavaScriptAddSstractivity,形成thebasisofmodernWebemodernWebExexperiences。

    HTML,CSS和JavaScript的角色:核心職責 HTML,CSS和JavaScript的角色:核心職責 Apr 08, 2025 pm 07:05 PM

    HTML定義網頁結構,CSS負責樣式和佈局,JavaScript賦予動態交互。三者在網頁開發中各司其職,共同構建豐富多彩的網站。

    Gitee Pages靜態網站部署失敗:單個文件404錯誤如何排查和解決? Gitee Pages靜態網站部署失敗:單個文件404錯誤如何排查和解決? Apr 04, 2025 pm 11:54 PM

    GiteePages靜態網站部署失敗:404錯誤排查與解決在使用Gitee...

    HTML中起始標籤的示例是什麼? HTML中起始標籤的示例是什麼? Apr 06, 2025 am 12:04 AM

    AnexampleOfAstartingTaginHtmlis,beginSaparagraph.startingTagSareEssentialInhtmlastheyInitiateEllements,defiteTheeTheErtypes,andarecrucialforsstructuringwebpages wepages webpages andConstructingthedom。

    如何用CSS3和JavaScript實現圖片點擊後周圍圖片散開並放大效果? 如何用CSS3和JavaScript實現圖片點擊後周圍圖片散開並放大效果? Apr 05, 2025 am 06:15 AM

    實現圖片點擊後周圍圖片散開並放大效果許多網頁設計中,需要實現一種交互效果:點擊某張圖片,使其周圍的...

    HTML,CSS和JavaScript:Web開發人員的基本工具 HTML,CSS和JavaScript:Web開發人員的基本工具 Apr 09, 2025 am 12:12 AM

    HTML、CSS和JavaScript是Web開發的三大支柱。 1.HTML定義網頁結構,使用標籤如、等。 2.CSS控製網頁樣式,使用選擇器和屬性如color、font-size等。 3.JavaScript實現動態效果和交互,通過事件監聽和DOM操作。

    網頁批註如何實現Y軸位置的自適應佈局? 網頁批註如何實現Y軸位置的自適應佈局? Apr 04, 2025 pm 11:30 PM

    網頁批註功能的Y軸位置自適應算法本文將探討如何實現類似Word文檔的批註功能,特別是如何處理批註之間的間�...

    See all articles