腾讯第二批---第五题
递归：（超时）
#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;
} 
