头像

东边的西瓜皮

gggg




离线:7小时前


最近来访(80)
用户头像
Lucky_1002
用户头像
kk12930
用户头像
就爱摆烂_3
用户头像
SoupHu
用户头像
小松鼠1996
用户头像
pydmy7
用户头像
Ele
用户头像
走向新世界
用户头像
钉宫无路赛
用户头像
啥都不会做
用户头像
arch_hui
用户头像
Honoka_sxr
用户头像
no_one
用户头像
chenx
用户头像
C++Rookie.
用户头像
StarLi9ht
用户头像
无人生还
用户头像
tleee
用户头像
只道寻常_4
用户头像
塘桥夜话

活动打卡代码 AcWing 479. 加分二叉树

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
int a[N];
int f[N][N];
int root[N][N];
void dfs(int l,int r){
    if(l>r)return;
    int k=root[l][r];
    cout<<k<<' ';
    dfs(l,k-1);
    dfs(k+1,r);
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        scanf("%d", &a[i]);
        f[i][i]=a[i];
        root[i][i]=i;
        f[i][i-1]=1;
    }  
    f[n+1][n]=1;
    for(int w=2;w<=n;w++){
        for(int i=1;i+w-1<=n;i++){
            int j=i+w-1;
            for(int k=i;k<=j;k++){
                int t=f[i][k-1]*f[k+1][j]+a[k];
                if(t>f[i][j]){
                    f[i][j]=t;
                    root[i][j]=k;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    dfs(1,n);
    cout<<endl;

}


活动打卡代码 AcWing 320. 能量项链

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 256;
int a[N];
int f[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )scanf("%d",&a[i]);
    for(int i=n;i<2*n;i++)a[i]=a[i-n];
    for(int w=3;w<=n+1;w++){
        for(int i=0;i+w-1<n*2;i++){
            int j=i+w-1;
            for(int k=i+1;k<j;k++){
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)ans=max(ans,f[i][i+n]);
    cout<<ans;
}


活动打卡代码 LeetCode 32. 最长有效括号

动态规划

忽略边界条件

    if s[i]== ')':
        if s[i-1]=='(':
            dp[i]= dp [i-2]+2
        else
            dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size();
        int dp[n+3];
        memset(dp,0,sizeof dp);
        int ans=0;
        for(int i=2;i<=n;i++){
            if(s[i-1]==')'){
                if(s[i-2]=='(')dp[i]=dp[i-2]+2;
                else {
                    int idx = i-dp[i-1]-2;
                    if(idx>=0)
                        if(s[idx]=='(')
                            dp[i]=dp[i-1]+2+dp[idx];
                }
                ans=max(ans,dp[i]);
            }
        }
        return ans;

    }
};

双向统计

当从左向右时,不考虑形如”((())”,左括号多于右括号的情况
当从右向左时,不考虑形如”(()))”,右括号多于左括号的情况
统计左括号和右括号,相等时更新最值。
假设存在最长括号串S,则S必由”S)“或者“(S”包围

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size();
        int l=0,r=0;
        int lcnt=0,rcnt=0;
        int ans=0;
        while(r<n){
            while(r<n&&lcnt>=rcnt){
                if (s[r++]=='(')lcnt++;
                else rcnt++;
                if(lcnt==rcnt)ans=max(ans,lcnt+rcnt);
            }
            l=r,lcnt=0,rcnt=0;
        }
        l=r=n-1,lcnt=rcnt=0;
        while(l>=0){
            while(l>=0&&rcnt>=lcnt){
                if(s[l--]=='(')lcnt++;
                else rcnt++;
                if(lcnt==rcnt)ans=max(ans,lcnt+rcnt);
            }
            r=l,lcnt=0,rcnt=0;
        }
        return ans;

    }
};


活动打卡代码 AcWing 524. 愤怒的小鸟

思路总结

  1. $y=ax^2+bx$,要求$a<0$,三个点确定一条抛物线,原点已经确定,另外两个点可以构成$O(n^2)$量级条抛物线
  2. 预处理出所有的抛物线,判断其所经过的所有点,用bitmap存下来。注意横坐标不能相等,还有只经过一条点的抛物线的特殊处理,可以假设其只经过一个点,因为在最优解中,无非必要,尽量多占几个点。
  3. 按bitmap从$1$到$1<<n$遍历,注意,只要遍历到第一个未击中的点,用这个点更新即可break。这里可以break的原因如下,假设f[i]的最优解已经知道,则j点是必须经过的,我们遍历所有经过j点的抛物线,最优解一定被包含了。这个地方值得好好玩味一下。
#include <iostream>
#include <cstring>
#include<cmath>
#include <algorithm>
using namespace std;
const int N = 18;
const int M = 1<<N;
int f[M];
double x[N],y[N];
int path[N][N];
int cmp(double a,double b){
    if(fabs(a-b)<1e-8)return 0;
    else if(a>b)return 1;
    else return -1;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for (int i = 0; i < n; i ++ ){
            cin>>x[i]>>y[i];
        }
        memset(path,0,sizeof path);
        for (int i = 0; i < n; i ++ ){
            path[i][i]=1<<i;
            for (int j = 0; j < n; j ++ ){
                if(!cmp(x[i],x[j]))
                    continue;
                double a = (y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
                double b = (y[j]/x[j]-a*x[j]);
                if(cmp(a,0)>=0)continue;
                for(int k = 0;k<n;k++){
                    if(!cmp(y[k],(a*x[k]+b)*x[k])){
                        path[i][j]|=(1<<k);
                    }
                }
            }
        }
        memset(f,0x3f,sizeof f);
        f[0]=0;
        for(int i=0;i+1<1<<n;i++){
            for(int j=0;j<n;j++){
                if(!((i>>j)&1)){
                    for(int k=0;k<n;k++){
                        f[i|path[j][k]]=min(f[i|path[j][k]],f[i]+1);
                    }
                    break;
                }
            }
        }
        cout<<f[(1<<n)-1]<<endl;
    }

}


活动打卡代码 LeetCode 752. 打开转盘锁

struct Node{
    int a[4];
};
int dist[10][10][10][10];
Node tar;
class Solution {
public:
    static int calc(Node t){
            int res=0;
            for(int i=0;i<4;i++){
                res+=min(abs(t.a[i]-tar.a[i]),10-abs(t.a[i]-tar.a[i]));
            }
            return dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]+res;
        };
    struct cmp{
        bool operator()(const Node &a,const Node &b){
            return calc(a)>calc(b);
        }
    };
    int openLock(vector<string>& deadends, string target) {
        tar={{target[0]-'0',target[1]-'0',target[2]-'0',target[3]-'0'}};


        memset(dist,0,sizeof dist);
        for(auto &t:deadends){
            dist[t[0]-'0'][t[1]-'0'][t[2]-'0'][t[3]-'0']=-1;
        }
        priority_queue<Node,vector<Node>,cmp> q;

        if(dist[0][0][0][0]==-1)return -1;
        dist[0][0][0][0]=1;
        q.push({{0,0,0,0}});
        while(q.size()){
            auto t=q.top();
            q.pop();
            if(t.a[0]==tar.a[0]&&t.a[1]==tar.a[1]&&t.a[2]==tar.a[2]&&t.a[3]==tar.a[3])return dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]-1;
            for(int k=0;k<4;k++){
                int d[]={-1,1};
                for(int j=0;j<2;j++){
                    Node tmp=t;
                    tmp.a[k]+=d[j];
                    if(tmp.a[k]>=10)tmp.a[k]-=10;
                    else if(tmp.a[k]<0)tmp.a[k]+=10;
                    if(dist[tmp.a[0]][tmp.a[1]][tmp.a[2]][tmp.a[3]]==0){
                        dist[tmp.a[0]][tmp.a[1]][tmp.a[2]][tmp.a[3]]=dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]+1;
                        q.push(tmp);
                    }
                }
            }
        }
        return -1;
    }
};


活动打卡代码 AcWing 1068. 环形石子合并

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 512;
int a[N];
int f[N][N],g[N][N];
int s[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        scanf("%d", &a[i]);
        a[i+n]=a[i];
    }
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n*2;i++){
        s[i]=s[i-1]+a[i];
        g[i][i]=0;
    }

    for(int w=1;w<=n*2;w++){
        for(int i=1;i+w-1<=n*2;i++){
            int j=i+w-1;
            for(int k=i;k<j;k++){
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    int minv=0x3f3f3f3f,maxv=-1;
    for (int i = 1; i <= n; i ++ )minv=min(g[i][i+n-1],minv),maxv=max(maxv,f[i][i+n-1]);
    printf("%d\n%d",minv,maxv);

}


活动打卡代码 AcWing 292. 炮兵阵地

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 128;
int arr[N];
char str[10];
vector<int> legal_state;
int f[N][1<<10][1<<10];
int count(int val){
    int ans=0;
    while(val){
        ans+=1;
        val&=(val-1);
    }
    return ans;
}
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ){
        scanf("%s",str);
        for(int j=0;j<m;j++){
            arr[i]<<=1;
            if(str[j]=='H'){
                arr[i]|=1;
            }
        }
        //cout<<arr[i]<<endl;
    }
    for(int i=0;i<1<<m;i++){
        if((i&(i>>1))||(i&(i>>2))){
            ;
        }else{
            legal_state.push_back(i);
        }
    }

    for(int i=2;i<n+2;i++){
        for(auto a:legal_state)for(auto b:legal_state){
            if((a&b)==0){
                for(auto c:legal_state){
                    if((a&c)==0&&(b&c)==0&&(c&arr[i-2])==0){
                        f[i&1][b][c]=max(f[i&1][b][c],f[(i+1)&1][a][b]+count(c));
                    }
                }
            }
        }
    }
    int ans=0;
    for(auto a:legal_state)for(auto b:legal_state){
        ans=max(ans,f[(n+1)&1][a][b]);
    }
    printf("%d",ans);

}


活动打卡代码 AcWing 327. 玉米田

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1<<12,M=12*12+2;
int f[14][M][N];
const int MOD=1e8;
vector<int> state;
vector<int> next_state[N];
int cnt[N];
bool check(int val){
    if(val&(val>>1))return false;
    else return true;
}
int mt[14];
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            int val;
            scanf("%d", &val);
            mt[i]<<=1;
            mt[i]|=val;
        }
    }
    for (int i = 0; i < 1<<m; i ++ ){
        if(check(i)){
            state.push_back(i);
        }
        cnt[i]=cnt[i>>1]+(i&1);
    }
    for(auto s:state){
        for(auto j:state){
            if((s&j)==0)next_state[s].push_back(j);
        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<=m*n;j++){
            for(auto s:state){
                for(auto ns:next_state[s]){
                    if((s&mt[i-1])==s&&j-cnt[s]>=0){
                        f[i][j][s]+=f[i-1][j-cnt[s]][ns];
                        f[i][j][s]%=MOD;
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n*m;i++)ans=(ans+f[n+1][i][0])%MOD;
    cout<<ans;

}



注意到先合并和较小的两个的结果一般较优,考虑是否能按先合并小的来求最小值,这种方法是错误的
示例:

3 2 2 3-> 3 4 3-> 7 3->10 |4+7+10=21
5 5 ->10 ->5+5+10=20


活动打卡代码 AcWing 1064. 小国王

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1<<12;
long long f[12][102][N];
int legal[N];
int cnt[N];
vector<int> shift[N];
int c;
bool check(int val){
    return !(val&(val>>1));
}
int count(int val){
    int res=0;
    while(val){
        res++;
        val&=(val-1);
    }
    return res;
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<1<<n;i++){
        if(check(i)){
            legal[c++]=i;
            cnt[i]=count(i);
        }

    }

    for(int i=0;i<c;i++){
        int v=legal[i];
        int t=(v<<1)|v|(v>>1);
        for(int j=0;j<c;j++){
            int w=legal[j];
            if((t&w)==0)shift[v].push_back(w);

        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<=k;j++){
            for(int k=0;k<c;k++){
                int s=legal[k];
                for(auto t:shift[s]){
                    if(j-cnt[s]>=0){
                        f[i][j][s]+=f[i-1][j-cnt[s]][t];
                    }
                }

            }
        }
    }
    cout<<f[n+1][k][0];
    return 0;


}