여름방학-동적 기획 I-(C-무료 파이)

1112 단어 dp
한 개의 탑 유형의 문제는 처음에 어떻게 시작해야 할지 몰랐는데 (문제가 너무 적으면 부족해야 한다) 나중에 문제를 풀고 보니 탑 문제였다. dp[i][j]를 위치로 정의할 수 있다. i가 j초에 얻을 수 있는 파이설을 풀고 방정식을 바꾸어 밑에서 위로 올라가는 방식으로 답을 구할 수 있다.
/*
   ,      。
   dp[i][j]  :  i  j          。
     dp[i][j]  ,     i,  j。      [maxt]           。
      dp[5][0]。
  i=0 i=10     。
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int dp[11][MAXN];
int n,x,t,maxt;
int mymax(int a,int b)
{
	if(a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
int main()
{
	while(scanf_s("%d",&n)!=EOF&&n)
	{
		maxt=0;
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++)
		{
			scanf_s("%d %d",&x,&t);
			dp[x][t]++;//   dp[i][j].
			maxt= maxt>t?maxt:t;
		}
		for(int j=maxt-1;j>=0;j--)//         dp[i][j].
		{
			dp[10][j]+=mymax(dp[10][j+1],dp[9][j+1]);
			dp[0][j]+=mymax(dp[0][j+1],dp[1][j+1]);
			for(int i=1;i<=9;i++)
			{
				dp[i][j]+=mymax(dp[i][j+1],mymax(dp[i+1][j+1],dp[i-1][j+1]));
			}
		}
		printf("%d
",dp[5][0]); } return 0; }

좋은 웹페이지 즐겨찾기