HDU - 1565 규격 디스패치 DP

1422 단어 DP
제목:
n*n의 칸에서 수를 뽑고 두 냥이 서로 인접하지 않는 것을 얻어 최대의 총계를 구한다
한 줄에서 두 개의 인접하지 않은 상태를 충족시키기 -> 현재 상태 & 현재 상태에서 한 자리를 왼쪽으로 이동합니다. 결과가 0이면 조건을 충족시키고, 그렇지 않으면 st수 그룹에 저장되지 않습니다.
예: 1011010 | 11110
그리고 dp로 처리해 주세요.
st[j] & st[k]==0 세로 방향이 서로 인접하지 않도록 보증
dp[i][j]+=dp[i-1][k]+sumdp[i][j]는 두 개의 서로 인접하지 않은 상태를 만족시킬 때 도달할 수 있는 최대치인sum가 제j개의 상태수의 총계임을 나타낸다
 
AC 코드
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i=a;i--)
#define fori(x) for(int i=0;i

typedef long long ll;
const int maxn=1e6+7;
const int mod=1e9+7;
const double eps=1e-8;
// const double pi = acos(-1);

using namespace std;

int a[22][22];
int dp[22][1<<22];
int st[1<<22];

int main()
{
    int n;
    while(sca(n)!=EOF)
    {
      rep(i,0,n)
      {
        rep(j,0,n)
        {
          sca(a[i][j]);
        }
      }
      int cnt = 0;
      rep(i,0,(1<

 

좋은 웹페이지 즐겨찾기