程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3257（Cow Roller Coaster）DP

poj3257（Cow Roller Coaster）DP

編輯：C++入門知識

題意：要連出一個從1-L的過山車線，給出n段可選的建設方案。每段都有起始位置，終止位置，代價，和樂趣程度。要實現1-L的長度中，相鄰兩端要首尾相連，總建設代價控制在B之內，問最多能獲得多少樂趣程度。


解法：二維dp， num[i][j]記錄恰好建設到i並且用掉代價j多能獲得的最多樂趣。先將每段可選方案按照位置排序，然後進行轉移。最後選max(num[L][i]),i from 0 to B;

代碼：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define eps 1e-8
typedef long long LL;


struct point
{
    int s,e,fun,cost;
} points[10010];
bool operator<(point a,point b)
{
   if(a.s!=b.s)
        return a.sb)
                continue;
                LL &tool=num[points[i].e][j+points[i].cost];
                 tool=max(tool,num[points[i].s-1][j]+points[i].fun);
         }
     }
 }
 LL ans=-1;
 for(int i=0;i<=b;i++)
     ans=max(ans,num[L][i]);
   cout<
  1. 上一頁:
  2. 下一頁:
C++入門知識
ARP報文發送的可視化實現，arp報文可視化

ARP報文發送的可視化實現，arp報文可視化一、安裝VS20
BZOJ 1507 Editor

真是一個牛b的頭文件...... Edito
1064. Complete Binary Search Tree (30)

分析： 　　考察BST + 完全二叉樹的性質，注意： 　　　
linux 下cmake 編譯 ,調用,調試 poco 1.6.0 小記，cmake1.6.0

linux 下cmake 編譯 ,調用,調試 poco 1.
C++混合編程之idlcpp教程Lua篇(5)，idlcpplua

C++混合編程之idlcpp教程Lua篇(5)，idlcpp
C++混合編程之idlcpp教程Lua篇(6)，idlcpplua

C++混合編程之idlcpp教程Lua篇(6)，idlcpp
相關文章
閱讀排行榜
C++編程 –安全並發訪問容器元素 從operator&lt;&lt;談函數重載決議 Palindrome Partitioning II -- LeetCode POJ 2442 Sequence 窗口分割，mfc窗口分割 QT5中的pro文件中為何要加入&quot;QT += widgets&quot;，qt5widgets linux c++應用程序內存高或者占用CPU高的解決方案_20161213，linux_20161213 hdu 5139 (離線處理) 畫矩形 掃雷核心算法c++實現 [LeetCode] Remove Element (三種解法)
熱門圖文
php數據類型轉換，php數據類型 each-Coins 多重背包 poj 2195 Going Home 二分圖最小權匹配KM算法 php 5.3新特性介紹 一些實用的圖形用戶界面方法 .Net語言 APP開發平台——Smobiler學習日志：如何快速實現類似於微信的懸浮顯示二維碼效果，appsmobiler asp.net Get和Post傳參和接收參數，asp.net接收參數 PHP獲取文件後綴名的三個函數
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved