CodeForces 981D - Bookshelves(선형 패브릭 dp)

제목: n개의 수를 k조로 나누어 각조의sum값을 구하고 연산의 최대값을 구합니다.
사고방식: 높은 위치에서 낮은 위치로 체크를 하는데 분명히 어떤 사람이 1을 얻을 수 있을 때 최대치는 반드시 1을 얻는다.
문제는 check로 바뀌었다. 이미 check가 받은 높은 위치의 값을 만족시키는 상황에서 현재 위치가 1을 얻을 수 있는지 판단한다.
연산의 성질로 인해 어떤 자리를 1로 하려면 서로 어울리는 수가 반드시 이 자리에서도 1이어야 하기 때문에 dp로 해답을 구할 수 있다.
정의 상태 dp(i, j): [1,i]수는 j조로 나뉘고 만족 조건값은 1이다.
상태 전이 방정식: dp(i, j) = dp(k-1, j-1) & 고위 만족 & 현재 위치 = 1//([k, i]를 제j조 수로 화합)

#include 

using namespace std;
typedef long long ll;
const int maxn = 55;

ll a[maxn], s[maxn];
ll ans;
int n, m;
bool dp[maxn][maxn];

ll sum(int l, int r) {
    return s[r] - s[l-1];
}

bool check(int x) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= i; ++j) {
            for(int k = j; k <= i; ++k) {
                dp[i][j] |= dp[k-1][j-1] && ((sum(k, i)&ans) == ans) && (sum(k, i) & ((ll)1<> n >> m) {
        for(int i = 1; i <= n; ++i) {
            cin >> a[i];
            s[i] = s[i-1] + a[i];
        }
        ans = 0;
        for(int i = 56; i >= 0; --i) {
            if(check(i)) ans |= ((ll)1<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Codeforces 1287C Garland

제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CodeForces 981D - Bookshelves(선형 패브릭 dp)

좋은 웹페이지 즐겨찾기