腾讯第二批---第五题

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>
#include <stack>

using namespace std;

void helperCnt(int index,int t, int& res, int a, int b) {
	if (index > b) return;
	if (index >= a){
		res += 1;
	}
	//代表选择了红花
	helperCnt(index + 1, t, res, a, b);
	//代表选择了白花
	helperCnt(index + t, t, res, a, b);
}
int getTotalRes(int a, int b,int t) {
	int res = 0;
	helperCnt(0, t, res, a, b);
	return res;
}
int getRes(vector<int>& v, int a, int b) {
	int res = 0;
	for (int i = b; i >= a; i--) {
		res += v[i];
	}
	return res;
}
int main() {
	int n, t;
	cin >> n >> t;
	int a, b;
	vector<pair<int, int> > v;
	while (n--) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	vector<int> res;
	for (auto itm : v) {
		res.push_back(getTotalRes(itm.first, itm.second,t));
	}
	for (auto itm : res) {
		cout << itm << endl;
	}
	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>
#include <stack>

using namespace std;

int getRes(vector<int>& v, int a, int b) {
	int res = 0;
	for (int i = b; i >= a; i--) {
		res += v[i];
	}
	return res;
}
int main() {
	int n, t;
	cin >> n >> t;
	int a, b;
	vector<pair<int, int> > v;
	while (n--) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	//假设最多共1000朵花
	int m = 1000;
	vector<int> dp(m + 1, 0);
	dp[0] = 1;
	for (int i = 1; i <= m; i++) {
		if (i < t) dp[i] = dp[i-1];
		else dp[i] = dp[i - 1] + dp[i - t];
	}
	vector<int> res;
	for (auto itm : v) {
		res.push_back(getRes(dp, itm.first, itm.second));
	}
	for (auto itm : res) {
		cout << itm << endl;
	}
	return 0;
}