创客更新装备 动态规划

创客更新装备

时间限制: 1 Sec  内存限制: 128 MB

题目描述

创客的装备有点老旧啦，所以老师想给创客更新装备。

每个显示屏都有它的固有属性——刷新频率 T 和价格 S。

现在有 N 台显示屏可供选择，老师想购置 3 台新的显示屏放在创客。

老师对于购买显示屏的要求是：

    1.对 N 台显示屏按照输入顺序标号为1，2，3 ... N。

    2.对于购买的3个显示屏的编号 i < j < k 需要满足 Ti < Tj < Tk。

    3.需要购买的显示屏总价格最小。

你能算出购买到符合老师要求的 3 台显示屏最少需要多少钱吗？

输入

输入包括多组测试样例。

对于每组测试样例：

第一行输入一个正整数 N ，表示有 N 台显示屏可供选择。（1 <= N <= 3000）。

第二行输入 N 个正整数，第 i 个数字表示第 i 台显示屏的刷新频率 Ti。（1 <= Ti <= 109）

第三行输入 N 个正整数，第 i 个数字表示第 i 台显示屏的价格 Si。（1 <= Si <= 108）

输出

对于每组测试样例输出占一行，输出结果为可花费的最小价格。

如果无法购买到合适的 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

提示

在第一个示例中，您可以选择第 1，第 4 和第 5 台显示屏，因为 T1 < T4 <  T5，（ 2 < 4 < 10），价格是 40 + 10 + 40 = 90。 
在第二个示例中，没有办法购置 3 台合适的显示屏，因此答案为 -1。

//dp[0][i]表示以第i台电脑为结尾，买1台电脑的花费 //dp[1][i]表示以第i台电脑为结尾，买2台电脑的花费 //dp[2][i]表示以第i台电脑为结尾，买3台电脑的花费 #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++){//已枚举经购买电脑的个数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++){//因为要买三台电脑，所以i从3开始Min = min(Min,dp[2][i]);//dp[2][i]表示以第i台为结尾，买三台电脑的最小花费}if(Min == INF) printf("-1\n");else printf("%d\n",Min);}return 0; }

 

总结

以上是生活随笔为你收集整理的创客更新装备 动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。