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