| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
蒟蒻丑陋的动规代码,神犇轻喷……#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dp(int m,int n,int a,int b,int c,int ans[102][102]);
void prin(int m,int n,int a,int b,int c,int ans[102][102]);
int getmin(int a,int b);
int main(int argc,char *argv[])
{
int a,b,c,ans[102][102],path[102][102];
memset(ans,-1,sizeof(ans));
scanf("%d%d%d",&a,&b,&c);
if(dp(0,0,a,b,c,ans)==1<<30)
printf("impossible\n");
else
{
printf("%d\n",dp(0,0,a,b,c,ans));
prin(0,0,a,b,c,ans);
}
return (0);
}
int dp(int m,int n,int a,int b,int c,int ans[102][102])
{
if(m>a||n>b||m<0||n<0)
return (1<<30);
if(ans[m][n]!=-1)
return (ans[m][n]);
if(m==c||n==c)
return (ans[m][n]=0);
ans[m][n]=1<<30;
ans[m][n]=getmin(ans[m][n],dp(a,n,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(m,b,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(0,n,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(m,0,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(m+n,0,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(a,m+n-a,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(0,m+n,a,b,c,ans)+1);
ans[m][n]=getmin(ans[m][n],dp(m+n-b,b,a,b,c,ans)+1);
return (ans[m][n]);
}
void prin(int m,int n,int a,int b,int c,int ans[102][102])
{
if(m==c||n==c||ans[m][n]==1<<30)
return;
if(ans[m][n]==ans[a][n]+1)
{
printf("FILL(1)\n");
prin(a,n,a,b,c,ans);
}
else if(ans[m][n]==ans[m][b]+1)
{
printf("FILL(2)\n");
prin(m,b,a,b,c,ans);
}
else if(ans[m][n]==ans[0][n]+1)
{
printf("DROP(1)\n");
prin(0,n,a,b,c,ans);
}
else if(ans[m][n]==ans[m][0]+1)
{
printf("DROP(2)\n");
prin(m,0,a,b,c,ans);
}
else if(m+n<=a&&ans[m][n]==ans[m+n][0]+1)
{
printf("POUR(2,1)\n");
prin(m+n,0,a,b,c,ans);
}
else if(m+n-a>=0&&ans[m][n]==ans[a][m+n-a]+1)
{
printf("POUR(2,1)\n");
prin(a,m+n-a,a,b,c,ans);
}
else if(m+n<=b&&ans[m][n]==ans[0][m+n]+1)
{
printf("POUR(1,2)\n");
prin(0,m+n,a,b,c,ans);
}
else if(m+n-b>=0&&ans[m][n]==ans[m+n-b][b]+1)
{
printf("POUR(1,2)\n");
prin(m+n-b,b,a,b,c,ans);
}
}
int getmin(int a,int b)
{
return (a<b?a:b);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator