题目描述

一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。

输入样例:

5

输出样例:

7

算法1

(完全背包) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
map<string,int>M;
int main(){
    int t;
    cin>>t;
   M["Beijing"]=8;
    M["Washington"]=-5;
    M["London"]=0;
    M["Moscow"]=3;
    for(int i=1;i<=t;i++)
    {
        int h,m;
        int city1h,city2m;
        int city2h,coty2m;
        int ans_h;
        string time;
        string city1,city2;
        string ans_day="Today";
        scanf("%d:%d ",&h,&m);
        cin>>time;
        cin>>city1>>city2;
        if(time=="AM")
            h=h%12;
        else if(time=="PM"&&h==12);
        else h=h+12;
            //转weiLondom
        city1h=h;

        auto a = M[city1];
        auto b = M[city2];
       // cout<<a<<"_"<<b<<endl;
        if(a>b)
        {
            city2h=city1h-(a-b);
        }
        else if(a==b)city2h=city1h;
        else
        {
            city2h=city1h+(b-a);
        }
      //  cout<<city1h<<"_"<<city2h<<endl;
        if(city1h>=0&&city2h<24)ans_day="Today";
        if(city1h>=0&&city2h<0)ans_day="Yesterday";
        if(city1h>=0&&city2h>=24)ans_day="Tomorrow";

        if(city2h<0&&city2h>=-12)
        {
            ans_h=12+city2h;
            if(ans_h==0)ans_h=12;
            time = "PM";
        }
        else if(city2h>=-24&&city2h<-12)
        {
            ans_h=24+city2h;
            if(ans_h==0)ans_h=12;
            time = "AM";
        }
        else if(city2h>=0&&city2h<12)
        {
            ans_h=city2h;
            if(ans_h==0)ans_h=12;
            time = "AM";
        }
         else if(city2h>=12&&city2h<24)
        {
            ans_h=city2h-12;
            if(ans_h==0)ans_h=12;
            time = "PM";
        }
         else if(city2h>=24&&city2h<36)
        {
            ans_h=city2h-24;
            if(ans_h==0)ans_h=12;
            time = "AM";
        }
         else if(city2h>=36&&city2h<48)
        {
            ans_h=city2h-36;
            if(ans_h==0)ans_h=12;
            time = "PM";
        }
        cout<<"Case "<<i<<": "<<ans_day<<" ";
        printf("%d:%.2d ",ans_h,m);
        cout<<time<<endl;

    }
    return  0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla