創(chuàng)客更新裝備

時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB

題目描述

創(chuàng)客的裝備有點(diǎn)老舊啦，所以老師想給創(chuàng)客更新裝備。

每個(gè)顯示屏都有它的固有屬性——刷新頻率 T 和價(jià)格 S。

現(xiàn)在有 N 臺顯示屏可供選擇，老師想購置 3 臺新的顯示屏放在創(chuàng)客。

老師對于購買顯示屏的要求是：

? ? 1.對 N 臺顯示屏按照輸入順序標(biāo)號為1，2，3 ... N。

? ? 2.對于購買的3個(gè)顯示屏的編號 i < j < k 需要滿足 Ti?< Tj?< Tk。

? ? 3.需要購買的顯示屏總價(jià)格最小。

你能算出購買到符合老師要求的 3 臺顯示屏最少需要多少錢嗎？

輸入

輸入包括多組測試樣例。

對于每組測試樣例：

第一行輸入一個(gè)正整數(shù) N ，表示有 N 臺顯示屏可供選擇。（1 <= N <= 3000）。

第二行輸入 N 個(gè)正整數(shù)，第 i 個(gè)數(shù)字表示第 i 臺顯示屏的刷新頻率 Ti。（1 <= Ti?<= 109）

第三行輸入 N?個(gè)正整數(shù)，第 i 個(gè)數(shù)字表示第 i 臺顯示屏的價(jià)格 Si。（1 <= Si?<= 108）

輸出

對于每組測試樣例輸出占一行，輸出結(jié)果為可花費(fèi)的最小價(jià)格。

如果無法購買到合適的 3 臺顯示屏，輸出 -1。

樣例輸入

5 2 4 5 4 10 40 30 20 10 40 3 100 101 100 2 4 5 10 1 2 3 4 5 6 7 8 9 10 10 13 11 14 15 12 13 13 18 13

樣例輸出

90 -1 33

提示

在第一個(gè)示例中，您可以選擇第 1，第 4 和第 5 臺顯示屏，因?yàn)?T1?< T4?<? T5，（ 2 < 4 < 10），價(jià)格是 40 + 10 + 40 = 90。?
在第二個(gè)示例中，沒有辦法購置 3 臺合適的顯示屏，因此答案為 -1。

//dp[0][i]表示以第i臺電腦為結(jié)尾，買1臺電腦的花費(fèi) //dp[1][i]表示以第i臺電腦為結(jié)尾，買2臺電腦的花費(fèi) //dp[2][i]表示以第i臺電腦為結(jié)尾，買3臺電腦的花費(fèi) #include<iostream> #include<cstdio> using namespace std; #define INF 0x3fffffff const int maxn = 1005; int t[maxn];//每臺電腦的頻率 int dp[4][maxn]; int main() {int n;while(scanf("%d",&n) != EOF){for(int i = 0;i < 4; i++){fill(dp[i],dp[i] + maxn, INF);}for(int i = 1;i <= n; i++){scanf("%d",&t[i]);}for(int i = 1;i <= n; i++){scanf("%d",&dp[0][i]);}for(int i = 0;i < 3; i++){//已枚舉經(jīng)購買電腦的個(gè)數(shù)for(int j = i;j <= n; j++){for(int k = 1;k <= j; k++){if(t[j] > t[k])dp[i][j] = min(dp[i][j],dp[i - 1][k] + dp[0][j]);}}}int Min = INF;for(int i = 3;i <= n; i++){//因?yàn)橐I三臺電腦，所以i從3開始Min = min(Min,dp[2][i]);//dp[2][i]表示以第i臺為結(jié)尾，買三臺電腦的最小花費(fèi)}if(Min == INF) printf("-1\n");else printf("%d\n",Min);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的创客更新装备 动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。