poj3666

poj 3666 Making the Grade
제목 링크:http://poj.org/problem?id=3666
참고:https://blog.csdn.net/wuyanyi/article/details/7255154
제목
최소한 의 대가 로 단 조 롭 게 늘 어 나 지 않 거나 단 조 롭 게 줄 어 들 지 않 는 서열 을 정 하 다
문제 분석
dp [i] [j]: = 앞 i + 1 개 수로 구 성 된 서열 이 고 서열 의 최대 치 는 j 이 며 dp [i] [j] 는 해당 하 는 cost 를 대표 합 니 다.
상태 이동 방정식: dp [i] [j] = abs (j - w [i]) + min (dp [i - 1] [k])   (k<=j)
dp 이동 배열:
w[i]
i\j
1
2
3
4
5
6
7
8
9
1
0
0
3
1
2
1
0
2
2
3
1
1
4
3
6
3
2
1
5
4
10
6
4
2
1
3
5
12
7
4
3
3
9
6
20
14
10
8
7
6
5
4
3
복잡 도 O (nm ^ 2)
개선: 표 에서 dp [i] [j] = abs (j - w [i]) + min (dp [i - 1] [k])   (k < = j) 여기 있 는 k 는 1 에서 j 로 옮 겨 다 닐 필요 가 없습니다. j 를 for 순환 할 때 dp [i - 1] [j] 의 최소 값 mn = min (mn, dp [i - 1] [j]) 을 계속 업데이트 한 다음 에 dp [i] [j] = abs (j - w [i]) + mn 을 계속 업데이트 하면 됩 니 다. 개선 후 복잡 도 는 O (nm) 로 바 꿀 수 있 습 니 다.
하지만 여기 m 는 w [i] 의 최대 치 입 니 다. 분명히 TLE 입 니 다.
그래서 분 산 된 사상 으로 개선 하고 복잡 도 를 O (n ^ 2) 로 바 꿔 야 합 니 다.
이산 화: 서열 을 정렬 하고 j 를 원래 의 값 에서 서열 배열 로 표시 합 니 다. 즉, 위치의 전후 관계 로 값 을 만 듭 니 다.
매번 dp [i] 를 업데이트 할 때마다 dp [i] 와 dp [i - 1] 만 사용 하기 때문에 스크롤 배열 을 이용 하여 공간 복잡 도 를 최적화 할 수 있 습 니 다.
스크롤 배열 (두 배열 을 스크롤 하여 중복 이용)
예 를 들 어 dp [i + 1] [j] = max (dp [i] [j], dp [j - w [i]]] + v [i])
이 전달 식 에서 dp [i + 1] 계산 시 dp [i] 와 dp [i + 1] 만 필요 하기 때문에 패 리 티 와 결합 하여 다음 과 같은 형식 으로 쓸 수 있 습 니 다.

int dp[2][MAX_W+1]; //dp  
void solve()
{
	for(int i=0;i

코드

//poj3666 Marking the Grade
//      ，                    
//  :DP+   
#include 
#include 
#include 
#define Abs(a) ((a>0)?(a):-(a))
using namespace std;
const int N=2005;
const long long int INF=(1<<60);
int n;
int a[N],b[N];
long long int dp[4][N];
void solve()
{
    for(int j=0;j>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	solve();
	return 0;
}