DP(최적화 주제 - 사각형 부등식 최적화 1)
제목: 몇 무더기의 돌들이 한 바퀴로 둘러싸여 있는데 두 무더기의 돌을 합칠 때마다 답안에 이 두 무더기의 무게를 기여하고 답안의 최대치와 최소치를 물어본다.
>> face <<
상태: d p m i n [l] [r] → dpmin [l] [r] \to dpmin [l] [r] → 해당 구간 내 최소 수익, d p m a x [l] [r] → dpmax [l] [r] \to dpmax [l] [r] → 해당 구간 최대 수익
목표: d p m i n [1] [n] & d p m a x [1] [n] dpmin[1] [n] \ & dpmax[1] [n] dpmin[1] [n] & dpmin[1] [n]
경계: 첫 번째 이전의 공헌은 모두 돌무더기에서 제공됩니다.경계(기억화 검색)를 추가로 제공할 필요가 없다. 구간을 최소화하기 위해서는 먼저memset(dpmin, ∞\infty∞,sizeof(dpmin))을 확보한 다음에 dp m i n [i] [i] = 0,i∈[1,2∈n] dpmin[i] [i] = 0,i\in[1,2*n] dpmin[i][i]=0,i∈[1,2?n]
합법적 판단
전이 방정식: 구간 dp, 모든 것을 알 수 없는 상태로 옮길 수 있도록 매거진
{ d p m i n [ l ] [ r ] = m i n ( d p m i n [ l ] [ r ] , d p m i n [ l ] [ k ] + d p m i n [ k + 1 ] [ r ] ) + ∑ i = l i ≤ r a [ i ] ; d p m a x [ l ] [ r ] = m a x ( d p m a x [ l ] [ r ] , d p m a x [ l ] [ k ] + d p m a x [ k + 1 ] [ r ] ) + ∑ i = l i ≤ r a [ i ] ;\begin{dcases} dpmin[l][r] = min(dpmin[l][r], dpmin[l][k] + dpmin[k+1][r]) +\sum_{i = l}^{i\leq r} a[i];\\[2ex] dpmax[l][r] = max(dpmax[l][r], dpmax[l][k] + dpmax[k+1][r]) +\sum_{i = l}^{i\leq r} a[i];\end{dcases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r])+i=l∑i≤ra[i];dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r])+i=l∑i≤ra[i];
attention: 링 체인화(길이 2*n의 체인으로 변환)
2배 경험치:
Strategy: 구간 dp (사각형 부등식으로 최적화)
일단 사나이 블로그를 붙여볼게요.
상태: d p m i n [l] [r] → dpmin [l] [r] \to dpmin [l] [r] → 해당 구간 내 최소 수익, d p m a x [l] [r] → dpmax [l] [r] \to dpmax [l] [r] → 해당 구간 최대 수익
목표: d p m i n [1] [n] & d p m a x [1] [n] dpmin[1] [n] \ & dpmax[1] [n] dpmin[1] [n] & dpmin[1] [n]
경계: 첫 번째 이전의 공헌은 모두 돌무더기에서 제공됩니다.경계(기억화 검색)를 추가로 제공할 필요가 없다. 구간을 최소화하기 위해서는 먼저memset(dpmin, ∞\infty∞,sizeof(dpmin))을 확보한 다음에 dp m i n [i] [i] = 0,i∈[1,2∈n] dpmin[i] [i] = 0,i\in[1,2*n] dpmin[i][i]=0,i∈[1,2?n]
합법적 판단
전이 방정식: 구간 dp, 모든 것을 알 수 없는 상태로 옮길 수 있도록 매거진
{ d p m i n [ l ] [ r ] = m i n ( d p m i n [ l ] [ r ] , d p m i n [ l ] [ k ] + d p m i n [ k + 1 ] [ r ] ) + ∑ i = l i ≤ r a [ i ] ; d p m a x [ l ] [ r ] = m a x ( d p m a x [ l ] [ r ] , d p m a x [ l ] [ k ] + d p m a x [ k + 1 ] [ r ] ) + ∑ i = l i ≤ r a [ i ] ;\begin{dcases} dpmin[l][r] = min(dpmin[l][r], dpmin[l][k] + dpmin[k+1][r]) +\sum_{i = l}^{i\leq r} a[i];\\[2ex] dpmax[l][r] = max(dpmax[l][r], dpmax[l][k] + dpmax[k+1][r]) +\sum_{i = l}^{i\leq r} a[i];\end{dcases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r])+i=l∑i≤ra[i];dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r])+i=l∑i≤ra[i];
attention: 링 체인화(길이 2*n의 체인으로 변환)
2배 경험치:
Strategy: 구간 dp (사각형 부등식으로 최적화)
일단 사나이 블로그를 붙여볼게요.
#include
#include
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 2e3 + 9;
const int mod = 1e6 + 3;
int dpmin[maxn][maxn], n, a[maxn], dpmax[maxn][maxn], sum[maxn];
int main()
{
ios::sync_with_stdio(0);
int n;
cin >> n;
met(dpmin, oo);
_rep(i, 1, n)
{
cin >> a[i];
a[i + n] = a[i];
dpmin[i][i] = dpmin[i + n][i + n] = 0;
}
_rep(i, 1, 2*n){
sum[i] = sum[i-1] + a[i];
}
_rep(len, 2, n)
{
_rep(l, 1, 2 * n - len + 1)
{
int r = l + len - 1;
_rep(k, l, r-1){
dpmax[l][r] = max(dpmax[l][k] + dpmax[k+1][r] + sum[r] - sum[l-1], dpmax[l][r]);
dpmin[l][r] = min(dpmin[l][k] + dpmin[k+1][r] + sum[r] - sum[l-1], dpmin[l][r]);
}
}
}
int min_val = oo, max_val = 0;
_rep(i, 1, n)
{
min_val = min(dpmin[i][i + n - 1], min_val);
max_val = max(max_val, dpmax[i][i + n - 1]);
}
cout << min_val << endl
<< max_val << endl;
}
그리고 표로 의사결정의 단조성을 판단한다
#include
#include
#include
#include
#include
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 2e3 + 9;
const int mod = 1e6 + 3;
int dpmin[maxn][maxn], n, a[maxn], dpmax[maxn][maxn], sum[maxn], kma[maxn][maxn], kmi[maxn][maxn];
int main()
{
ios::sync_with_stdio(0);
int n;
cin >> n;
met(dpmin, oo);
_rep(i, 1, n)
{
cin >> a[i];
a[i + n] = a[i];
dpmin[i][i] = dpmin[i + n][i + n] = 0;
}
_rep(i, 1, 2 * n) {
sum[i] = sum[i - 1] + a[i];
kmi[i][i] = kma[i][i] = i;
}
_rep(len, 2, n)
{
_rep(l, 1, 2 * n - len + 1)
{
int r = l + len - 1;
_rep(k, l, r - 1) {
/*dpmax[l][r] = max(dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1], dpmax[l][r]);
dpmin[l][r] = min(dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1], dpmin[l][r]);*/
if (dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1] > dpmax[l][r]) {
dpmax[l][r] = dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1];
kma[l][r] = k;
}
if (dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1] < dpmin[l][r]) {
dpmin[l][r] = dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1];
kmi[l][r] = k;
}
}
}
}
_rep(i, 1, n + 1) {
_rep(j, i+1, i + n-1) {
assert(kma[i][j - 1] <= kma[i][j] && kma[i][j] <= kma[i + 1][j]);
//assert(kmi[i][j - 1] <= kmi[i][j] && kmi[i][j] <= kmi[i + 1][j]);
}
}
}
kmi만 정책 결정의 단조성을 만족시키고 kma는 만족시키지 못하는 것을 발견하였다
그러나 dpmax는 하나의 성질이 있는데 어떤 dpmax[l][r]에 대해서는 k=l 또는 k=r-1만 가장 크다
사실 가장 작은 것도 성질이 있는데, k가 l과 r 사이에 있을 때도 가장 작은 것을 취할 수 있다
최적화 후 코드
#include
#include
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 2e3 + 9;
const int mod = 1e6 + 3;
int dpmin[maxn][maxn], n, a[maxn], dpmax[maxn][maxn], sum[maxn], s[maxn][maxn] ; //s[i][j] dpmin[i][j] k
int main()
{
ios::sync_with_stdio(0);
int n;
cin >> n;
met(dpmin, oo);
_rep(i, 1, n)
{
cin >> a[i];
a[i + n] = a[i];
dpmin[i][i] = dpmin[i + n][i + n] = 0;
}
_rep(i, 1, 2 * n)
{
sum[i] = sum[i - 1] + a[i];
s[i][i] = i;
}
_rep(len, 2, n)
{
_rep(l, 1, 2 * n - len + 1)
{
int r = l + len - 1;
dpmax[l][r] = max(dpmax[l+1][r]+dpmax[l][l], dpmax[l][r-1]+dpmax[r][r]) + sum[r] - sum[l-1];
int K, tmp = oo;
_rep(k, s[l][r-1], s[l+1][r]){
int tt = dpmin[l][k] + dpmin[k+1][r] + sum[r] - sum[l-1];
if(tt < tmp){
tmp = tt;
K = k;
}
}
s[l][r] = K;
dpmin[l][r] = tmp;
}
}
int min_val = oo, max_val = 0;
_rep(i, 1, n)
{
min_val = min(dpmin[i][i + n - 1], min_val);
max_val = max(max_val, dpmax[i][i + n - 1]);
}
cout << min_val << endl
<< max_val << endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3233 [Ahoi 2013] 동전 찾기(선형 체 + dp)
[문제풀이]
본연은 줄곧 2차원 dp를 생각하고 있었는데, 문제풀이를 보고서야 1차원으로 f[i]를 최대 액면가가 i로 설정할 수 있다는 것을 발견했을 때, 모든 토끼종이를 사서 쓴 최소 동전의 수를
f[i]=min...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
최적화 후 코드
#include
#include
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 2e3 + 9;
const int mod = 1e6 + 3;
int dpmin[maxn][maxn], n, a[maxn], dpmax[maxn][maxn], sum[maxn], s[maxn][maxn] ; //s[i][j] dpmin[i][j] k
int main()
{
ios::sync_with_stdio(0);
int n;
cin >> n;
met(dpmin, oo);
_rep(i, 1, n)
{
cin >> a[i];
a[i + n] = a[i];
dpmin[i][i] = dpmin[i + n][i + n] = 0;
}
_rep(i, 1, 2 * n)
{
sum[i] = sum[i - 1] + a[i];
s[i][i] = i;
}
_rep(len, 2, n)
{
_rep(l, 1, 2 * n - len + 1)
{
int r = l + len - 1;
dpmax[l][r] = max(dpmax[l+1][r]+dpmax[l][l], dpmax[l][r-1]+dpmax[r][r]) + sum[r] - sum[l-1];
int K, tmp = oo;
_rep(k, s[l][r-1], s[l+1][r]){
int tt = dpmin[l][k] + dpmin[k+1][r] + sum[r] - sum[l-1];
if(tt < tmp){
tmp = tt;
K = k;
}
}
s[l][r] = K;
dpmin[l][r] = tmp;
}
}
int min_val = oo, max_val = 0;
_rep(i, 1, n)
{
min_val = min(dpmin[i][i + n - 1], min_val);
max_val = max(max_val, dpmax[i][i + n - 1]);
}
cout << min_val << endl
<< max_val << endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3233 [Ahoi 2013] 동전 찾기(선형 체 + dp)[문제풀이] 본연은 줄곧 2차원 dp를 생각하고 있었는데, 문제풀이를 보고서야 1차원으로 f[i]를 최대 액면가가 i로 설정할 수 있다는 것을 발견했을 때, 모든 토끼종이를 사서 쓴 최소 동전의 수를 f[i]=min...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.