最强DE 战斗力 （nyoj 541）

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

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

网上的数学解题链接：http://blog.csdn.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 int N = 1010;
    BigInteger d[] = new BigInteger[N];
    Scanner cin = new Scanner(System.in);
    
    public static void main(String[] args) {
        int t, n;
        t = cin.nextInt();
        for(int i=0; i<N; i++)
            d[i] = new BigInteger("0");
        for(int i= 1; i<=N-2; i++){
            d[i] = BigInteger.valueOf(i);
            for(int j=1; j<=i/2; j++){
                d[i] = d[i].max(d[j].multiply(d[i-j]));
            }
        }
        while(t-- > 0){
            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)
{
    if(n <= 0)return; 
    for(int i=0; i<n; i++){
        int c = 0;
        for(int k=0; k<N; k++){
            ans[k] = ans[k]*3+c;
            c = ans[k]/MOD; 
            if(ans[k] >= MOD)
                ans[k] %= MOD; 
        } 
    } 
}

void muti(int n){
    for(int i=0; i<N; i++)
        ans[i] = ans[i]*n;
    int c = 0;
    for(int i=0; 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, 0, sizeof(ans));
        ans[0] =1;
        cin>>m;
        if(m%3 != 1){
            mutify(m/3);
        }else {// if(m%3 == 1)
            mutify(m/3-1);
            if(m > 1) muti(4);
        }
        if(m%3 == 2){
            muti(2);
        }
        int k = N-1;
        while(ans[k] == 0) k--;
        for(int i=k; i>=0; i--){
            cout<<ans[i];
        }
        cout<<endl;
        
    }    
    return 0;
}