状态转移很有新鲜感, 我没想到, 难道是我变弱了?

n>1时, dp[n][e][d]=min{ dp[n-1][e-p][d-p] }
n==1时, dp[1][e][d]=min{ dp[1][e-p^2][d-p] }

速度可以分段, 和路程的关系比较纠结, 列个方程算不出来 = =

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

int orz(int dp[21][101][101],int n,int e,int d) {
    if(dp[n][e][d]!=-1)
        return dp[n][e][d];
    if(e<d)
        return 2e9;
    if(d==0)
        return 0;
    if(e==0)
        return 2e9;

    dp[n][e][d]=2e9;
    switch(n) {
        case 1:
            for(int p=1;p<=(int)sqrt((double)e);p++)
                dp[n][e][d]=min(orz(dp,n,e-p*p,d-p)+1,dp[n][e][d]);
            break;
        default:
            for(int p=1;p<=d;p++)
                dp[n][e][d]=min(dp[n][e][d],orz(dp,n-1,e-p,d-p)+orz(dp,1,e,p));
            break;
    }

    return dp[n][e][d];
}

int main() {
    int N,E,D;
    scanf("%d%d%d",&N,&E,&D);

    int dp[21][101][101];
    memset(dp,0xff,sizeof(dp));

    printf("%d",orz(dp,N,E,D));

    return 0;
}