最强DE 战斗力 （nyoj 541）

题解链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=541

几天前百度题解后用数学知识AC的，后来大牛说这是一道动态规划题。

网上的数学解题链接：http://blog.****.net/x314542916/article/details/8204583

d(i) = max{d(j)*d(n-j) | 1<= j <=n/2};

用Java写比较简单

import java.math.BigInteger;
import java.util.Scanner;

public class Main{

    final ;
    BigInteger d[] = new BigInteger[N];
    Scanner cin = new Scanner(System.in);

    public static void main(String[] args) {
        int t, n;
        t = cin.nextInt();
        ; i<N; i++)
            d[i] = ");
        ; i<=N-; i++){
            d[i] = BigInteger.valueOf(i);
            ; j<=i/; j++){
                d[i] = d[i].max(d[j].multiply(d[i-j]));
            }
        }
        ){
            n = cin.nextInt();
            System.out.println(d[n].toString());
        }
    }
}

用数学知识的解题代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x7fffffff
#define N 10000
#define MOD 10

int ans[N];

void mutify(int n)
{
    )return;
    ; i<n; i++){
        ;
        ; k<N; k++){
            ans[k] = ans[k]*+c;
            c = ans[k]/MOD;
            if(ans[k] >= MOD)
                ans[k] %= MOD;
        }
    }
}

void muti(int n){
    ; i<N; i++)
        ans[i] = ans[i]*n;
    ;
    ; i<N; i++){
        ans[i] = ans[i]+c;
        c = ans[i]/MOD;
        ans[i] %= MOD;
    }
}

int main()
{
    int t, m, n;
    cin>>t;
    while(t--) {
        memset(ans, , sizeof(ans));
        ans[] =;
        cin>>m;
         != ){
            mutify(m/);
        }else {// if(m%3 == 1)
            mutify(m/-);
            ) muti();
        }
         == ){
            muti();
        }
        ;
        ) k--;
        ; i--){
            cout<<ans[i];
        }
        cout<<endl;

    }
    ;
}