vijos1037 쌍탑 구축 - 상태 최적화 dp

전송문
제목 대의: 자체 참조
문제 풀이:
이 문제는 초보자가 생각하기에 매우 적합하다!!!
문제풀이를 보지 말고 먼저 기본적인 방법을 생각해 보고 한 걸음 한 걸음 최적화할 것을 건의합니다.
자, 말씀드리겠습니다.
우리는 우선'도달할 수 있을지'의 문제만 고려할 것이다. (처음에 나는 ppt에서 보았기 때문에 ppt에서 너에게 최대 높이를 구하라고 말하지 않았기 때문이다).
일단 첫눈에 01가방 타당성 문제 아닌가요?
그리고 문제는 모든 물건이 탑 하나만 짓는 데 쓰일 수 있다는 것을 보증할 수 없다는 것이다. 왜 그런지 생각해 보자.
그리고 dp[n][m1][m2]로 바꾸면 두 탑의 높이가 각각 m1m2라는 뜻이다.
복잡도 O (n*m^2)는 분명히 TLE입니다.
그리고 알고리즘의 병목은 상태가 번잡하기 때문에 m1m2를 합병하는 것을 고려한다.(n은 분명히 합병할 수 없는 것이고 m1m2는 또 이렇게 닮았기 때문이다)
그리고 안 할 거예요. 상태전환 방정식에서 손을 댈 수 있을까 했는데 갑자기 m1m2의 차이가 현재의hi라면 좋지 않을까요?!
다시 말하면 우리는 그들의 구체적인 값에 관심이 없고 단지 그들의 차이에 관심이 있을 뿐이다!
그 다음 작은 처리는 m1-m2가 마이너스일 수도 있지만, 분명히 |m1-m2|<=sigma {hi} (M으로 기록) 이 있다.
그래서 dp[n][m]로 m1-m2+M=m의 상황을 나타낸다.
m1=m2 즉 m=M.
전이란 dp[n][m]와 dp[n-1][m-h[i]]|dp[n-1][m+h[i]]|dp[n-1][m]이다.
초기 dp[0][m]=true, 기타 =false.
그리고 문제를 보러 갔는데 높이가 더 필요했어.
그것도 하기 쉽다. dp[n][m]는 현재 상황에서 두 탑의 높이의 합이 얼마나 되는지 표시한다(분명히 두 탑의 높이의 합차를 알면 두 탑의 높이를 확정할 수 있다).
그리고 -1로 존재하지 않는다는 것을 표시한다(즉 이전의false).
그럼 옮기기는if(from>=0)를 추가하면 됩니다.합이기 때문에 마지막 출력은/2입니다.
여기요.
코드:

//
#include
#include
#include
#define MAXN 110
#define MAXM 4100
using namespace std;
int dp[MAXN][MAXM],h[MAXN];
int main()
{
	int n,m=0;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		m+=h[i];
	}
	for(int i=0;i<=2*m;i++)
		dp[0][i]=-1;
	dp[0][m]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=2*m;j++)
		{
			dp[i][j]=-1;
			if(j-h[i]>=0&&dp[i-1][j-h[i]]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-h[i]]+h[i]);
			if(j+h[i]<=2*m&&dp[i-1][j+h[i]]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j+h[i]]+h[i]);
			if(dp[i-1][j]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
//	for(int i=1;i<=n;i++,printf("
"))
//		for(int j=0;j<=2*m;j++)
//			printf("%d ",dp[i][j]);
	if(dp[n][m]>0) printf("%d
",dp[n][m]/2);
	else printf("Impossible
");
}