hdu 1565 격자 추출 수 (1) [상 압 dp]

체크 개수 (1)
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7585    Accepted Submission(s): 2861
Problem Description
n * n 칸 짜 리 바둑판 을 드 리 겠 습 니 다. 칸 마다 마이너스 가 있 습 니 다.
그 중에서 몇 개의 수 를 꺼 내 서 임의의 두 개의 수가 있 는 칸 이 공공 변 이 없 게 한다. 즉, 취 하 는 수가 있 는 두 개의 칸 이 서로 인접 하지 못 하고 취 하 는 수의 합 이 가장 크다 는 것 이다.
 
Input
여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 테스트 인 스 턴 스 는 하나의 정수 n 과 n * n 개의 비 마이너스 (n < 20) 를 포함한다.
 
Output
모든 테스트 인 스 턴 스 에 대해 출력 이 얻 을 수 있 는 가장 큰 합
 
 
Sample Input 3 75 15 21  75 15 28  34 70 5    Sample Output 188
Author
ailyanlu
 
Source
Happy 2007
 
생각:
dp [i] [j] 2 차원 배열 을 구축 하면 i 행 상 태 는 j 의 최대 수치 임 을 나타 내 고 그 상태 전이 방정식 을 내 놓 기 어렵 지 않다. dp [i] [j] = max (dp [i] [j], dp [i - 1] [k] + sum). 그 중에서 sum 은 j 상태 에서 의 수치 임 을 나타 낸다.
먼저 우 리 는 2 진법 의 표현 방법 을 알 아야 한다. e. g. j = = 5 일 때 101 을 나타 낸다. 즉, 첫 번 째 자리 와 세 번 째 자리 의 수 를 나타 내 고 두 번 째 자리 의 수 는 취하 지 않 는 다 는 것 이다.
그리고 우 리 는 매 거 진 방법 을 통 해 한 줄 에서 선택 할 수 있 는 방안 을 매 거 할 수 있다. 사실은 인접 한 1 이 있 는 상황 을 버 리 는 것 이다.그러면 우 리 는 비트 연산 으로 이 문 제 를 해결 할 수 있다.그렇다면 구체 적 으로 어떻게 실현 해 야 할 까?연산 (&) 과 계산 방식 이 같은 위치 에서 1 로 결 과 는 1 이 고 나머지 는 0 이다. 우 리 는 이렇게 한 방안 이 서로 인접 한 1 이 존재 할 수 있 는 지 를 판단 할 수 있다. 예 를 들 어 현재 상 태 는 j 이다.
j & (j < 1), 만약 지금 j = = 7
1 1 1&1 1 1 0=0110,
또 만약 지금 j = = 5
1 0 1&1 0 1 0 =0;
값 이 0 이 아니라면 인접 한 1 이 있 고 그렇지 않 으 면 없다 는 뜻 이다.이 부분의 코드 구현:

        for(int i=0; i

然后就是对于dp部分的处理，我们枚举每一行的状态j（j属于数组q），算出这一行这种状态j下的取值和，使得dp【i】【j】=sum。再枚举上一行的状态k，如果j状态和k状态没有上下相邻的1，那么就有：dp【i】【j】=max（dp【i】【j】，dp【i-1】【k】+sum）对于j状态和k状态能否有相邻的1.直接&即可。（刚刚把这种操作已经详解，这里不再啰嗦）。

对于这部分的代码实现：

        for(int i=0; i=1)
                for(int k=0; k

最后在第n-1行里边枚举一遍维护最大值即可。

另外注意一个问题，开1<<20的数组会MLE，因为我们直接枚举出cont个可以的方案（没有相邻1）其方案数不会达到这么大，所以我们数组也就不用开辣么大。

AC代码：

#include
#include
#include
using namespace std;
int a[25][25];
int dp[21][200000];
int q[200000];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for(int i=0; i=1)
                for(int k=0; k