P1028 数的计算

https://www.luogu.org/problem/P1028

 

#include <iostream> using namespace std; int dst[1001] = {0}; int main(void) { int n; cin>>n; dst[0] = 1; dst[1] = 1; for(int i = 2; i <= n; i++)//这里可以优化，计算到n/2即可 { int half = i/2; if(half>0) { for(int j = 0; j <= half; j++) { dst[i] += dst[j]; } } } cout << dst[n] << endl; }