POJ1157-동적 기획 꽃병 꽃꽂이

1603 단어 동적 기획
제목: f 송이의 꽃이 v 개의 꽃병에 꽂혀 있다...서로 다른 꽃이 서로 다른 꽃병에 꽂히면 서로 다른 미관 정도를 가지고 가장 큰 미관 정도를 추구한다. 그리고 제한 조건이 하나 있다. 예를 들어 i>j라면 번호가 i인 꽃이 꽂을 수 있는 꽃병의 번호도 번호가 j인 꽃이 꽂은 꽃병의 번호보다 커야 한다.(이 조건에 주의하지 않았기 때문에 나는 n을 오랫동안 생각했다~).
네, 아이디어를 말씀드리겠습니다.
제목의 뜻을 이해한 후에도 비교적 쓰기 쉽다. 여기에 꽃도 있고 꽃병도 있으니 틀림없이 2차원 dp를 썼을 것이다.dp[i][j]를 가정하면 i번째 꽃을 j번째 병에 꽂아 얻을 수 있는 최대 미관 정도, dp[i][j]=max(dp[i-1][k]+a[i][j]), k>=i-1&k 
 
#include "iostream"
using namespace std;
#define len 110
int main()
{
	int f,v;
	int i,j,k;
	int a[len][len];
	int dp[len][len];//dp[i][j]    i     j          dp[i][j]=max(dp[i-1][k]+a[i][k]);   
	scanf("%d",&f);
	scanf("%d",&v);
	for (i=0;i<f;i++)
	{
		memset(dp[i],0,sizeof(dp[i]));
		for (j=0;j<v;j++)
		{
			scanf("%d",&a[i][j]);
			if (i==0)
			{
				dp[i][j]=a[i][j];
			}
		}
		
	}
	
	for (i=1;i<f;i++)
	{
		for (j=i;j<v;j++)
		{
			int max=-999999;
			for (k=i-1;k<j;k++)
			{
				if (max<dp[i-1][k]+a[i][j])
				{
					max=dp[i-1][k]+a[i][j];
				}
			}
			dp[i][j]=max;
		}
	}

	int maxt=dp[f-1][0];

	for (i=0;i<v;i++)
	{
		if(maxt<dp[f-1][i])
			maxt=dp[f-1][i];
	}
	cout<<maxt<<endl;
	return 0;
}







좋은 웹페이지 즐겨찾기