Wi - Fi [Codeforces Round \ # 587 (Div. 3)] [선분 수 최적화 dp]

4504 단어 선분 수DP 동적 계획데이터 구조
제목 링크 [Codeforces 1216 F]
You work as a system administrator in a dormitory, which has ?n rooms one after another along a straight hallway. Rooms are numbered from 11 to ?n.
You have to connect all ?n rooms to the Internet.
You can connect each room to the Internet directly, the cost of such connection for the ?i-th room is ?i coins.
Some rooms also have a spot for a router. The cost of placing a router in the ?i-th room is also ?i coins. You cannot place a router in a room which does not have a spot for it. When you place a router in the room ?i, you connect all rooms with the numbers from ???(1, ?−?)max(1, i−k) to ???(?, ?+?)min(n, i+k) inclusive to the Internet, where ?k is the range of router. The value of ?k is the same for all routers.
Calculate the minimum total cost of connecting all ?n rooms to the Internet. You can assume that the number of rooms which have a spot for a router is not greater than the number of routers you have.
Input
The first line of the input contains two integers ?n and ?k (1≤?,?≤2⋅1051≤n,k≤2⋅105) — the number of rooms and the range of each router.
The second line of the input contains one string ?s of length ?n, consisting only of zeros and ones. If the ?i-th character of the string equals to '1' then there is a spot for a router in the ?i-th room. If the ?i-th character of the string equals to '0' then you cannot place a router in the ?i-th room.
Output
Print one integer — the minimum total cost of connecting all ?n rooms to the Internet.
  확실히, 시합 할 때 잉잉 거 릴 줄 몰랐어! 그 건 중요 하지 않 아!!! 관건 은... 흥!
  우선, 우 리 는 모든 점 에 대해 어떤 점 은 '1' (즉 공유 기 를 놓 는 것) 을 사용 할 수 있 고, 어떤 점 은 i 가치 링크 를 직접 사용 하여 인터넷 에 접속 하거나 다른 공유 기 에 수익 을 얻 을 수 있다 고 생각해 야 한다.
  그러면 우 리 는 먼저 공유 기 공간 을 설치 하지 않 은 점 을 고려 합 니 다. 이것 은 앞 에 공유 기 가 있 는 점 의 수익 자로 볼 수 있 거나 앞의 점 의 가치 와 i 를 직접적 으로 가지 고 조건 을 만족 시 킬 수 있 습 니까?
  그 다음 에 공유 기 를 놓 을 수 있 는 점 을 보면 그 가 치 는 어떻게 확인 해 야 합 니까? 앞의 [i - K, i - 1] 구간 을 찾 을 수 있 습 니 다. 공유 기 를 사용 하지 않 는 최소 치 를 찾 은 다음 에 [i - K - 1, i - 1] 구간 내의 사용 공유 기의 최소 치 를 비교 해서 계속 이렇게 내 려 가면 됩 니 다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, K;
ll  a[2][maxN<<2], dp[maxN][2];
char op[maxN];
void buildTree(ll *tree, int rt, int l, int r)
{
    tree[rt] = INF;
    if(l == r) return;
    int mid = HalF;
    buildTree(tree, Lson); buildTree(tree, Rson);
}
ll query(ll *tree, int rt, int l, int r, int ql, int qr)
{
    if(ql <= l && qr >= r) return tree[rt];
    int mid = HalF;
    if(qr <= mid) return query(tree, QL);
    else if(ql > mid) return query(tree, QR);
    else return min(query(tree, QL), query(tree, QR));
}
inline void pushup(ll *tree, int rt) { tree[rt] = min(tree[lsn], tree[rsn]); }
void update(ll *tree, int rt, int l, int r, int qx, ll val)
{
    if(l == r)
    {
        tree[rt] = val;
        return;
    }
    int mid = HalF;
    if(qx <= mid) update(tree, Lson, qx, val);
    else update(tree, Rson, qx, val);
    pushup(tree, rt);
}
int main()
{
    scanf("%d%d", &N, &K);
    scanf("%s", op + 1);
    buildTree(a[0], 1, 1, N);
    buildTree(a[1], 1, 1, N);
    dp[N][1] = INF; dp[0][0] = 0;
    for(int i=1; i<=N; i++)
    {
        if(i > 1) dp[i][0] = min(dp[i-1][0] + i, query(a[1], 1, 1, N, i - K, i - 1));
        else dp[i][0] = i;
        update(a[0], 1, 1, N, i, dp[i][0]);
        if(op[i] == '1')
        {
            if(i - K <= 1) dp[i][1] = i;
            else if(i > 1) dp[i][1] = min(query(a[1], 1, 1, N, i - K - 1, i - 1), query(a[0], 1, 1, N, i - K - 1, i - 1)) + i;
            update(a[1], 1, 1, N, i, dp[i][1]);
        }
    }
    printf("%lld
", min(dp[N][0], dp[N][1]));
    return 0;
}

Brute - Force 모드 매 칭 알고리즘 두 가지 실현 방식
Converting everything to and from wxString

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage