2019年4月

Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.

The current state of the wall can be respresented by a sequence a of n integers, with ai being the height of the i-th part of the wall.

Vova can only use 2×1 bricks to put in the wall (he has infinite supply of them, however).

Vova can put bricks only horizontally on the neighbouring parts of the wall of equal height. It means that if for some i the current height of part i is the same as for part i+1, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part 1 of the wall or to the right of part n of it).

Note that Vova can't put bricks vertically.

Vova is a perfectionist, so he considers the wall completed when:

all parts of the wall has the same height;
the wall has no empty spaces inside it.
Can Vova complete the wall using any amount of bricks (possibly zero)?

Input
The first line contains a single integer n (1≤n≤2⋅105) — the number of parts in the wall.

The second line contains n integers a1,a2,…,an (1≤ai≤109) — the initial heights of the parts of the wall.

Output
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.
解题关键:比version1多的处理点就是 只能相等且当前栈顶未消除的值不能比自身小否则永远无法消除。 最后还要判定一下残留的是否是最大值。

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stack>
using namespace std; 
int n,arr[2000000],res,mmax;
stack<int> s;
int main() {
    cin >> n;
    for(int i = 1; i<=n; i++){
        cin >> arr[i];
        mmax = max(arr[i], mmax);
        if(s.empty()){
            s.push(arr[i]);
        }else{
             if(s.top() < arr[i]){
                cout << "NO" << endl;
                return 0;
            }
            if(s.top() == arr[i]){
                s.pop();
            }
            else if(s.top() > arr[i]){
                s.push(arr[i]);
            }
        }
    }
    if(s.size()> 1){
        cout << "NO" << endl;
    }else if(s.size() == 1){
        if(s.top() < mmax){
            cout << "NO" << endl;
        }else{
            cout << "YES" << endl;
        }
    }else{
        cout << "YES" << endl;
    }
    return 0;
}

There is a house with n flats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of n integer numbers a1,a2,…,an, where ai=1 if in the i-th flat the light is on and ai=0 otherwise.

Vova thinks that people in the i-th flats are disturbed and cannot sleep if and only if 1<i<n and ai−1=ai+1=1 and ai=0.

Vova is concerned by the following question: what is the minimum number k such that if people from exactly k pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number k.

Input
The first line of the input contains one integer n (3≤n≤100) — the number of flats in the house.

The second line of the input contains n integers a1,a2,…,an (ai∈{0,1}), where ai is the state of light in the i-th flat.

Output
Print only one integer — the minimum number k such that if people from exactly k pairwise distinct flats will turn off the light then nobody will be disturbed.

解题关键:这个题实际上,如果出现“101”的情况,就优先去除右边的1,因为左边的1肯定是不影响这个0的,不然你怎么遍历过来的呢?

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std; 
int n, arr[1005];
int res;
int main() {
    cin >> n;
    for(int i = 1; i<=n; i++){
        cin >> arr[i];
    }
    for(int i = 2; i<n; i++){
        if(arr[i+1] == 1 && arr[i-1] == 1 && arr[i] == 0){
            arr[i+1] = 0;
            res ++;
        }
    }
    cout << res << endl;
    return 0;
}

Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.

The current state of the wall can be respresented by a sequence a of n integers, with ai being the height of the i-th part of the wall.

Vova can only use 2×1 bricks to put in the wall (he has infinite supply of them, however).

Vova can put bricks horizontally on the neighboring parts of the wall of equal height. It means that if for some i the current height of part i is the same as for part i+1, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part 1 of the wall or to the right of part n of it).

The next paragraph is specific to the version 1 of the problem.

Vova can also put bricks vertically. That means increasing height of any part of the wall by 2.

Vova is a perfectionist, so he considers the wall completed when:

all parts of the wall has the same height;
the wall has no empty spaces inside it.
Can Vova complete the wall using any amount of bricks (possibly zero)?

Input
The first line contains a single integer n (1≤n≤2⋅105) — the number of parts in the wall.

The second line contains n integers a1,a2,…,an (1≤ai≤109) — the initial heights of the parts of the wall.

Output
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.

解题关键: 转变思路只要两个相邻或相差二 就可以直接消掉,在消掉的前提下允许不能消掉1个 如2 5 3 因为后面两个可以把前面连带消掉 用堆栈模拟这个过程。

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stack>
using namespace std; 
int n,arr[2000000],res;
stack<int> s;
int main() {
    cin >> n;
    for(int i = 1; i<=n; i++){
        cin >> arr[i];
        if(s.empty()){
            s.push(arr[i]);
        }else{
            if(abs(arr[i] - s.top()) % 2 == 1){
                s.push(arr[i]);
            }else{
                s.pop();
            }
        }
    }
    if(s.size()> 1){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
    return 0;
}

多重背包、但是要用二进制优化,
二进制优化的原理就是比如数:13可以拆分为->1,2,4,6 我们可以用这四个数字表示1-13任何一个数字 1+2 = 3 1+4 = 5 1+2+4 =7 2+6=8 6+2+1 =9 4+6=10 6+4+1=11 6+4+2 = 12 所以就可以转换成01背包 只要对1246这四个数字选与不选就可以变成1-13的任何数字 举个例子如果选46不选12就得出10选14不选26就得出5以此类推 就可以转化成01背包

#include <iostream>
#include <cstring>
using namespace std; 
int dp[2000005], a[4000], b[4000], e, n,w[200005],v[200005],g;
int main(int argc, char** argv) {
    cin >> n;
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }
    for(int i = 1; i<=n; i++){
        cin >> b[i];
    }
    for(int i = 1; i<=n; i++){
        for(int k = 1; k<=b[i]; k=k<<1){
            w[++g] = k*a[i];
            v[g] = k;
            b[i] -= k;
        }
        if(b[i]){
            w[++g] = b[i]*a[i];
            v[g] = b[i];
        }
    }
    cin >> e;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i<=g; i++){
        for(int j = e; j >= w[i]; j--){
            dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[e] << endl;
    return 0;
}

http://oj.ldyzz.com.cn/problem/800
有向图找环 注意一个优化点就是 如果一个点在一个环中 那么他的ans 应该是等于环结束的点-环开始的点 无论这个点是否是开始的点。 所以只需要判断一次if(vis[v] == now) {return dep - c[v];} 遇到循环过的点可直接return inf; //因为之前此点的结果已经返回过。

#include <iostream>
#include <cstring>
#include <math.h>
#include <cstdio>
#include <stack>
using namespace std; 
int vis[200005],n,arr[200005],ans,now,c[200005];
const int inf = 0x3f3f3f;
inline int dfs(int v,int dep){
    if(vis[v] == now){
        return dep - c[v]; //之前走过 vis值等于now 所以直接dep - c[v] c[v] 表示之前走过的层级的数量 
    }
    if(vis[v]){
        return inf; //有环 但不是终点 证明此点永远不会到达自身 
    }
    vis[v] = now;
    c[v] = dep;
    dfs(arr[v], dep+1);
}
int main(int argc, char** argv) {
    scanf("%d", &n);
    ans = inf;
    for(int i = 1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    for(now = 1; now<=n; now++){
        ans = min(ans, dfs(now, 0));
    }
    cout << ans << endl;
    return 0;
}