首頁 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

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

    熱門文章

    <🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌
    北端:融合系統,解釋
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌
    Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌

    熱工具

    記事本++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教學
    1666
    14
    CakePHP 教程
    1425
    52
    Laravel 教程
    1323
    25
    PHP教程
    1272
    29
    C# 教程
    1251
    24
    了解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 18, 2025 am 12:09 AM

    HTML、CSS和JavaScript在Web開發中的作用分別是:1.HTML定義網頁結構,2.CSS控製網頁樣式,3.JavaScript添加動態行為。它們共同構建了現代網站的框架、美觀和交互性。

    HTML,CSS和JavaScript的未來:網絡開發趨勢 HTML,CSS和JavaScript的未來:網絡開發趨勢 Apr 19, 2025 am 12:02 AM

    HTML的未來趨勢是語義化和Web組件,CSS的未來趨勢是CSS-in-JS和CSSHoudini,JavaScript的未來趨勢是WebAssembly和Serverless。 1.HTML的語義化提高可訪問性和SEO效果,Web組件提升開發效率但需注意瀏覽器兼容性。 2.CSS-in-JS增強樣式管理靈活性但可能增大文件體積,CSSHoudini允許直接操作CSS渲染。 3.WebAssembly優化瀏覽器應用性能但學習曲線陡,Serverless簡化開發但需優化冷啟動問題。

    HTML的未來:網絡設計的發展和趨勢 HTML的未來:網絡設計的發展和趨勢 Apr 17, 2025 am 12:12 AM

    HTML的未來充滿了無限可能。 1)新功能和標準將包括更多的語義化標籤和WebComponents的普及。 2)網頁設計趨勢將繼續向響應式和無障礙設計發展。 3)性能優化將通過響應式圖片加載和延遲加載技術提升用戶體驗。

    HTML與CSS vs. JavaScript:比較概述 HTML與CSS vs. JavaScript:比較概述 Apr 16, 2025 am 12:04 AM

    HTML、CSS和JavaScript在網頁開發中的角色分別是:HTML負責內容結構,CSS負責樣式,JavaScript負責動態行為。 1.HTML通過標籤定義網頁結構和內容,確保語義化。 2.CSS通過選擇器和屬性控製網頁樣式,使其美觀易讀。 3.JavaScript通過腳本控製網頁行為,實現動態和交互功能。

    HTML:建立網頁的結構 HTML:建立網頁的結構 Apr 14, 2025 am 12:14 AM

    HTML是構建網頁結構的基石。 1.HTML定義內容結構和語義,使用、、等標籤。 2.提供語義化標記,如、、等,提升SEO效果。 3.通過標籤實現用戶交互,需注意表單驗證。 4.使用、等高級元素結合JavaScript實現動態效果。 5.常見錯誤包括標籤未閉合和屬性值未加引號,需使用驗證工具。 6.優化策略包括減少HTTP請求、壓縮HTML、使用語義化標籤等。

    HTML與CSS和JavaScript:比較Web技術 HTML與CSS和JavaScript:比較Web技術 Apr 23, 2025 am 12:05 AM

    HTML、CSS和JavaScript是構建現代網頁的核心技術:1.HTML定義網頁結構,2.CSS負責網頁外觀,3.JavaScript提供網頁動態和交互性,它們共同作用,打造出用戶體驗良好的網站。

    HTML:是編程語言還是其他? HTML:是編程語言還是其他? Apr 15, 2025 am 12:13 AM

    HTMLISNOTAPROGRAMMENGUAGE; ITISAMARKUMARKUPLAGUAGE.1)htmlStructures andFormatSwebContentusingtags.2)itworkswithcsssforstylingandjavascript for Interactivity,增強WebevebDevelopment。

    See all articles