2020-08-13 数的计算

https://www.luogu.com.cn/problem/P1028

下面注释掉的是想法,验证并且输出

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

long long qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}


int n;
int f[1001];//存每一位数的种类
string ans;
int cnt  = 0 ;
void found(int s){
    //insect str
//    stringstream sstr;
//    sstr<<s;
//    string c = sstr.str();
//    ans.insert(0, c);
//    cout<<ans<<" ";
    cnt++;
    for (int i = 1; i<=s/2; i++) {
        found(i);
//        ans.clear();
//        stringstream sstr;
//        sstr<<n;
//        string c = sstr.str();
//        ans.insert(0, c);
    }
}


int main(){
    n = read();
    found(n);
    //cout<<endl;
    cout<<cnt;
//    for(int i=1;i<=n;i++){ //1-n的递推
//        for(int j=1;j<=i/2;j++){
//            f[i]+=f[j]; //每一位叠加，递推走起
//        }
//        f[i]++; //加上本身
//    }
//    cout<<f[n];//输出n的种类
    return 0;
}
/*
3
 
============
5
*/

AC代码

#include<bits/stdc++.h>//万能头文件
using namespace std;
int n;
int f[1001];//存每一位数的种类
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){ //1-n的递推
        for(int j=1;j<=i/2;j++){
            f[i]+=f[j]; //每一位叠加，递推走起
        }
        f[i]++; //加上本身
    }
    cout<<f[n];//输出n的种类
    return 0;
}