Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

蒟蒻丑陋的动规代码,神犇轻喷……

Posted by YanXB at 2015-01-12 10:28:30 on Problem 3414
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator