[ACM] POJ 1946 解题报告, “非常好的DP”

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

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] }

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

代码:

[cpp]

#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;
}
[/cpp]

Asher.GG

git gut together

[ACM] POJ 1946 解题报告, “非常好的DP”

85 thoughts on “[ACM] POJ 1946 解题报告, “非常好的DP””

Leave a Reply Cancel reply