Balance POJ 1837

알림: 동적 기획, 01 가방
이 문 제 를 처음 본 첫 번 째 충동 은 궁 거 였 다...근 데 생각해 보면 안 될 거 야.
저도 선배 님 의 의견 을 보고 01 가방 이 떠 올 랐 어 요. 동적 기획 으로.
 
제목 의 대의:
천평 이 하나 있 는데 천평 좌우 양쪽 에 각각 몇 개의 갈고리 가 있 는데 모두 C 개의 갈고리 가 있 고 G 개의 갈고리 가 있 으 며 갈고리 코드 를 모두 갈고리 에 걸 어 천평 을 균형 있 게 하 는 방법의 총 수 를 구하 십시오.
그 중에서 막대 기 를 x 축 0 시 를 균형 점 으로 하 는 횡축 으로 볼 수 있다.
입력:
2 4 / C 갈고리 수 와 G 갈고리 수
- 23 / / 음수: 왼쪽 갈고리 가 천평 중앙 에서 의 거리;양수: 오른쪽 갈고리 가 천평 중앙 거리 c [k]
3, 4, 5, 8 / / G 개의 무 거 운 물건 의 질량 w [i]
 
 
dp 사고방식:
천평 중국 측 에 무 거 운 물건 이 있 을 때마다 천평 의 상 태 는 바 뀌 고 이 상 태 는 몇 가지 전 상태 에서 얻 을 수 있다.
 
우선 균형 도 j 의 개념 을 정의 합 니 다.
균형 도 j = 0 일 때 막대 가 균형 에 이 르 렀 음 을 나타 낸다. j > 0 은 막대 가 오른쪽 (x 축 오른쪽 반 축) 으로 기울 고 j < 0 은 반대 임 을 나타 낸다.
그러면 이때 균형 도 j 를 현재 막대 상 태 를 평가 하 는 값 으로 볼 수 있다.
따라서 하나의 상태 배열 dp [i] [j] 를 정의 할 수 있 습 니 다.
거리 c [i] 의 범 위 는 - 15 ~ 15 이 고 갈고리 무게 의 범 위 는 1 ~ 25 이 며 갈고리 수량 은 최대 20 이다.
따라서 가장 극단 적 인 균형 도 는 모든 물체 가 가장 먼 곳 에 걸 려 있 기 때문에 균형 도 최대 치 는 j = 15 * 20 * 25 = 7500 이다.원칙적으로 dp [1 ~ 20] [- 7500 ~ 7500] 가 있어 야 합 니 다.
따라서 아래 표 시 된 마이너스 가 나타 나 지 않도록 하나의 처 리 를 하여 배열 을 dp [1 ~ 20] [0 ~ 1500] 로 열 면 j = 7500 시 막대 가 균형 상태 가 된다.
 
그러면 매번 갈고리 코드 를 걸 면 균형 상태 에 미 치 는 영향 요 소 는 모든 갈고리 코드 의 힘 이다.
힘 의 팔 = 무게 * 팔 길이 = w [i] * c [k]
그러면 i 번 분동 을 걸 기 전에 막대 의 균형 도 는 j 이다.
   (다시 말 하면 앞의 i - 1 개의 갈고리 코드 를 모두 막대 에 걸 면 막대 의 균형 도 는 j)
그러면 i 번 째 갈고리 코드 를 걸 면 앞의 i 번 째 갈고리 코드 를 모두 막대 에 걸 면 막대 의 균형 도 j = j + w [i] * c [k]
   그 중에서 c [k] 는 막대 에 갈고리 가 달 린 위치 로 i 번 째 갈고리 가 서로 다른 위치 에 걸 려 있 으 면 서로 다른 균형 도 를 나타 낸다.
 
생각 하기 어렵 지 않 습 니 다. dp [i - 1] [j] 의 값 을 이미 알 고 있다 고 가정 하고 dp [i - 1] [j] = num 을 설정 합 니 다.
               (즉, 앞의 i - 1 개의 갈고리 코드 를 모두 막대 에 걸 고 상태 j 를 얻 는 방법 은 num 회 임 을 알 고 있 습 니 다)
   그러면 dp [i] [j + w [i] * c [k]] = dp [i - 1] [j] = num
(즉, 이 를 전제 로 k 번 째 갈고리 에 i 번 째 갈고리 코드 를 걸 면 상태 j + w [i] * c [k] 를 얻 는 방법 도 num 회)
 
여기까지 생각 하고 귀속 사상 을 이용 하면 상태 방정식 dp [i] [j + w [i] * c [k] = ∑ (dp [i - 1] [j])
어떤 선배 들 은 유도 방식 이 약간 다 르 기 때문에 얻 은 상태 방정식 은 dp [i] [j] = ∑ (dp [i - 1] [j - c [i] * w [i]]) 이다.
 
사실 두 방정식 은 등가 이다. 이것 은 간단하게 검증 할 수 있 고 두 번 째 방정식 을 먼저 유도 하면 반드시 첫 번 째 방정식 으로 전환 해 야 한다. 이것 은 아래 표 에 마이너스 가 나타 나 지 않도록 하기 위해 서 이다.
 
결론:
질문
상태 방정식 dp [i] [j + w [i] * c [k] = ∑ (dp [i - 1] [j])
초기 화: dp [0] [7500] = 1;   //어떤 무 거 운 물건 도 걸 지 않 을 때 막대 가 균형 을 이 루 는 것 이 한 방법 이다.
 
복잡 도 O (C * G * 15000)  충분히 받 아들 일 수 있다.

//Memory Time 
//1496K  0MS 

//         ，  dp             
// dp     ，                        
//      dp     ，      

#include<iostream>
using namespace std;

int dp[21][15001]; //    dp[i][j]
	                   //  （  ） i   （  ） ，  j      
int main(int i,int j,int k)
{
	int n;  //   
	int g;  //   
	int c[21];  //    
	int w[21];  //    

	
	/*Input*/

	cin>>n>>g;

	for(i=1;i<=n;i++)
		cin>>c[i];
	for(i=1;i<=g;i++)
		cin>>w[i];

	/*Initial*/

	memset(dp,0,sizeof(dp));  //              0
	dp[0][7500]=1;     //7500              
	                   //   0    ，        7500    1 ，      

	/*DP*/

	for(i=1;i<=g;i++)
		for(j=0;j<=15000;j++)
			if(dp[i-1][j])  //  ，   i-1      j            ，         
				            //        j
				for(k=1;k<=n;k++)
					dp[i][ j+w[i]*c[k] ] += dp[i-1][j]; //    
	
	/*Output*/

	cout<<dp[g][7500]<<endl;
	return 0;
}