A34896. 求个数
填空题
困难
知识点
题目描述
求个数
题目描述：
给定一组数据，及两个正整数N和M，求出数据中，值位于N到M之内的区间和的个数。
输入描述：
第一行输入一个正整数K（2≤K≤1000）
第二行输入K个正整数（-1000≤正整数≤1000），正整数之间以一个空格隔开
第三行输入两个正整数N和M（-1000≤正整数≤1000），表示区间，正整数之间以一个空格隔开
输出描述：
输出一个整数，表示满足要求的区间和个数
样例输入：
2
-1 3 -2
-1 2
样例输出：
3
参考答案
#include<iostream>
#include<algorithm>
using namespace std;
const int K = 1000; //维生装备模块数目最大值
const int M = 30; //氧气需要量最大值
const int N = 80; //燃料需要量最大值
const int INF = 100 * K + 1; // 全部装备模块的重量总和
struct Node {
int a; //第i个维生装备模块的氧气容量
int b; //i个维生装备模块的燃料容量
int c; //第i个维生装备模块的重量
} node[K + 1];
int f[M + 1][N + 1]; //f[i][j]表示前t个维生装备模块满足i氧气j燃料的维生装备模块重量最小值
int main() {
int m, n, k; //氧气、燃料、维生装备模块数
cin >> m >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> node[i].a >> node[i].b >> node[i].c;
}
//因为要求最小值，f[][]初始化为很大的正整数
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
f[i][j] = INF;
}
}
//0氧气0燃料的最小重量是0
f[0][0] = 0;
//01背包，逐个维生装备模块加入
for (int t = 1; t <= k; t++) {
for (int i = m; i >= 0; i--) { //氧气
for (int j = n; j >= 0; j--) { //燃料
//若燃料、氧气含量超过需求，可直接用需求量代换，不影响最优解
int i1 = min(i + node[t].a, m);
int j1 = min(j + node[t].b, n);
f[i1][j1] = min(f[i1][j1], f[i][j] + node[t].c);
}
}
}
cout << f[m][n] << endl;
return 0;
}答案解析
评分标准：
5分：能正确输出第一组数据；
5分：能正确输出第二组数据；
5分：能正确输出第三组数据；
5分：能正确输出第四组数据；
5分：能正确输出第五组数据；
5分：能正确输出第六组数据。
上一题
下一题