携程笔试 海豚题 过了88% 求大佬指点
用一个cnt数组来存放各个年龄的海豚，比如第x年的时候，cnt[0]存的是x-0岁的海豚，cnt[n]存的是x-n岁的海豚，这样不用每次去加，防止超时。
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<functional>
#include<vector>
#include<iostream>
#include<time.h>
#include<math.h>
using namespace std;
//-------------------------------------------------------
#define LL long long
//#define LL __int64
template<typename T>T Max(T a, T b){ return a>b ? a : b; }
template<typename T>T Min(T a, T b){ return a<b ? a : b; }
template<typename T>void Swap(T &a, T &b){ T c = a; a = b; b = c; }
template<typename T>T Abs(T a){ return a >= 0 ? a : -a; }
#define clr_all(a,b) memset(a,b,sizeof(a))
#define clr(a,b,n) memset(a,b,sizeof(a[0])*n)
const int MAXN = 100000 + 5;
const int MAXM = 500 + 5;
const int mod = 1000000007;
const int INF = 0x7FFFFFFF;
//-------------------------------------------------------
int cnt[MAXN];
int year[MAXN];
int main(){
int n, m, years, x;
scanf("%d%d", &n, &m);
cnt[0] = n;
scanf("%d", &years);
for (int i = 0; i < years; i++)
scanf("%d", &year[i]);
scanf("%d", &x);
sort(year, year + years);
for (int i = 1; i <= x; i++){
for (int j = 0; j < years && year[j] <= i; j++){
cnt[i] += cnt[-(year[j] - i)];
}
}
int ans = 0;
for (int i = (x>m ? x - m : 0); i < MAXN; i++)
ans += cnt[i];
printf("%d\n", ans);
return 0;
} 