poj 1946dp

제목: 한 팀에서 n마리의 젖소가 자전거를 타고 링을 뛴다. 만약에 1분에 x바퀴를 뛰면 선두 달리기는 x*x체력을 소모하고 뒤에서 따라다니는 것은 x체력을 소모한다.체력이 없는 소는 퇴장할 수 있고, 한 마리는 중점을 통과하면 경기를 완성할 수 있다.N, E, D 세 개의 수를 정해 N마리의 젖소가 있음을 나타내고, 한 마리의 젖소는 초기 에너지치 E를 가지며, D는 링이 필요한 링 수를 나타낸다.젖소가 라운드 경주를 완성할 수 있느냐고 물었다. 만약 안 된다면 0을 출력해야 한다. 그렇지 않으면 라운드 경주의 가장 짧은 시간을 출력해야 한다.
사고방식분명히 소 한 마리가 돌아가며 선두를 달리고 체력이 없으면 물러난다.dp[i][j][k]는 i마리 소가 선두를 달리고 있다(전 i-1마리는 퇴장), i마리 소는 j체력을 소모했고 팀은 k바퀴를 뛰는 데 필요한 최소 시간을 다 뛰었다.
그러면 dp[i][j][k]는 dp[i][j+a*a][k+a] 즉 현재 분에 a바퀴를 뛰고 한 번 갱신하지 않으면 즉시 dp[i+1][k+a]k+a]를 갱신할 수 있다. 이는 현재 분에 i두번째 소를 뛰고 퇴장한다는 뜻이다.마지막으로 3차원=D(즉 완주)의 최소 dp값을 봅시다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 105
int dp[22][N][N];
int n,e,m;
int main(){
    int i,j,k,a,res=INF;
    scanf("%d %d %d",&n,&e,&m);
    clr(dp, 0);
    for(i = 1;i<=n;i++)
        for(j = 0;j<=e;j++)
            for(k = 0;k<=m;k++)
                dp[i][j][k] = INF;
    dp[1][0][0] = 0;
    for(i = 1;i<=n;i++)
        for(j = 0;j<=e;j++)
            for(k = 0;k<=m;k++)
                for(a = 1;j+a*a<=e&&k+a<=m;a++){
                    dp[i][j+a*a][k+a] = min(dp[i][j+a*a][k+a],dp[i][j][k]+1);
                    dp[i+1][k+a][k+a] = min(dp[i+1][k+a][k+a],dp[i][j+a*a][k+a]);
                }
    for(i = 1;i<=n;i++)
        for(j = 1;j<=e;j++)
            if(dp[i][j][m])
                res = min(res,dp[i][j][m]);
    printf("%d
",res);
}