【bzoj3594】SCOI 2014 방백부의 옥수수밭 dp+2차원 나무형 수조 최적화

1465 단어
마치 매우 신기한 것 같아서 처음에는 그 결론을 발견하지 못했지만 결과는 모두 dp방정식으로 엉망진창으로 추측되었다.
매번 추가 조작의 구간 오른쪽 단점은 모두 n이어야 하는데, 왜?
우리는 만약에 중간 단락을 조작한다면 답안에 대한 영향은 앞 단락이 현재 단락에 대한 답안이 증가하고 현재 단락이 뒤 단락에 대한 답안이 감소하는 것을 고려한다.반면에 오른쪽 단점이 n을 얻으면 앞에 증가한 부분에 영향을 주지 않고 뒤에 줄어드는 영향을 주지 않기 때문에 오른쪽 단점이 n을 얻는 것이 가장 좋은 것이다.
그리고 우리는 dp를 할 수 있다. dp방정식은 매우 명백하다.
pp[i][j]는 앞의 i 개수가 j차 방안의 최대 답안을 사용했음을 나타낸다
dp[i][j]=max{dp[x][y]}+1 (x그리고 이동하는 순서에 주의해야 한다. 내부 순환은 거꾸로 매거해야 하며 01배낭을 유추해 볼 수 있다.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

int c[6010][510];
int dp[10010][510];
int a[10010];
int n,m,ans,mx;

int lowbit(int x)
{
	return x&(-x);
}

void modify(int x,int y,int z)
{
	for (int i=x;i<=mx+m;i+=lowbit(i))
	  for (int j=y;j<=m+1;j+=lowbit(j))
	    c[i][j]=max(c[i][j],z);
}

int query(int x,int y)
{
	int ans=0;
	for (int i=x;i;i-=lowbit(i))
	  for (int j=y;j;j-=lowbit(j))
	    ans=max(ans,c[i][j]);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	ans=0;
	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);mx=max(mx,a[i]);}
	for (int i=1;i<=n;i++)
	  for (int j=m;j>=0;j--)
	  {
	  	dp[i][j]=query(a[i]+j,j+1)+1;
	  	ans=max(ans,dp[i][j]);
	  	modify(a[i]+j,j+1,dp[i][j]);
	  }
	printf("%d
",ans); return 0; }

좋은 웹페이지 즐겨찾기