Gym - 100952H--H. Special Palindrome--dp 정수 구분(템플릿)

제목 주소 A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:
15 2 6 4 6 2 15
20 3 1 1 3 20
We have a special kind of palindromic sequences, let’s call it a special palindrome.
A palindromic sequence is a special palindrome if its values don’t decrease up to the middle value, and of course they don’t increase from the middle to the end.
The sequences above is NOT special, while the following sequences are:
1 2 3 3 7 8 7 3 3 2 1
2 10 2
1 4 13 13 4 1
Let’s define the function F(N), which represents the number of special sequences that the sum of their values is N.
For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
Your job is to write a program that compute the Value F(N) for given N’s.
Input The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.
Output Print one line for each given number N, which it the value F(N).
Examples Input 1 3 7 10 0 Output 1 2 5 17
제목 대의: F(n)는 숫자의 총수가 n과 같고 회문 문자열로 앞의 하위 문자열이 증가하고 뒤의 줄어드는 문자열의 수량이다(제목을 보면 알 수 있을 것이다).사고방식: 회문 문자열이기 때문에 모든 것은 c가 한쪽만 처리하면 되고 숫자는 반반이다.만약 문자열이 길이가 짝수라면 n의 수치는 짝수이어야 한다. 왜냐하면 양쪽의 총수는 같기 때문이다.우리는 먼저 dp를 처리하고 정수 구분을 미리 처리한다. f[i][j]는 1~i에서만 선택하고 총계는 j와 같은 방안수를 나타낸다.그리고 우리는 문자의 길이를 짝수와 홀수로 나누어 처리하면 된다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(a) ((a)&-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i=0;(i)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define se second

using namespace std;
typedef long long  ll;
typedef unsigned long long  ull;
typedef pair<int,int > pii;
const ll mod=10001;
const ll N =1e6+10;
const double eps = 1e-4;
const double pi=acos(-1);
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
int dx[4]={-1,0,1,0} , dy[4] = {0,1,0,-1};
ll f[351][351];
void solve()
{
    f[1][1] = 1;
    f[0][0] = 1;
    for (int i=2;i<=251;i++)
        for (int j=1;j<=i;j++)
            f[i][j]=(f[i-1][j-1]+f[i-j][j]);
    int n;

    while(cin>>n&&n)
    {
      ll ans=0;
      if(n%2==0)//        ，        n/2；
      {
          for(int i=1;i<=n/2;i++) ans+=f[n/2][i];
      }
      for(int i=n;i>=1;i-=2)//   ，         
      {
          for(int j=0;j<=i;j++) //          ，        
          {
              //cout<
              ans+=f[(n-i)/2][j];
          }
      }
        cout<<ans<<endl;
    }
}
int main()
{
   ios
   int T;
   //cin>>T;
   T=1;
   while(T--)
   {
       solve();
   }
}

정수 구분 템플릿: 상태 이동 방정식: f[i][j]=f[i-1][j]+f[i][j-i];

const int N = 1010;//  

int n;
int f[N];

int main()
{
    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) ;

    cout << f[n] << endl;

    return 0;
}

const int N = 1010;//   

int n;
int f[N][N];

int main()
{
    cin >> n;

    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) ;

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]);

    cout << res << endl;

    return 0;
}