第六周 6.21-6.27-白红宇

第六周 6.21-6.27

阅读量：4955 次

发布时间：2019-06-12

本文共 7562 字，大约阅读时间需要 25 分钟。

6.21

LIS有nlgn的算法。纯学dp。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 int num[5005],d[5005]; 6  7 int main(void) 8 { 9     int n; cin>>n;10     for(int i=0;i

Aguin

紫薯题。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 int dp[1005]; 6  7 struct node 8 { 9     int a,b;10 }edge[1005];11 12 bool cmp(node x,node y)13 {14     if(x.a!=y.a) return x.a
         
          >N;21     while(N--)22     {23         int n;scanf("%d",&n);24         for(int i=0;i

Aguin

6.22

UVA 103

升级版的n维矩形。打印一个路径就好。然而数据太亲民。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 int k,n,dp[30],G[30][30]; 7  8 struct BOX 9 {10     int no,edge[10];11 }box[30];12 13 bool cmp(BOX a,BOX b)14 {15     for(int i=0;i
          
           =box[i].edge[t]) {ok=0;break;}57                 if(ok) {G[j][i]=1; dp[i]=max(dp[i],dp[j]+1);}58             }59         }60         int ans=0,pos;61         for(int i=0;i
           
            ans) {ans=dp[i]; pos=i;}62 printf("%d\n",ans);63 ans_print(pos);64 printf("\n");65 }66 return 0;67 }

Aguin

6.23

发觉自己对dp的理解就有问题。紫薯啃的不明白。

文章也难找到合适的。

有的过于抽象。实例又容易固化思维。

稍微改了下就不会了。只能说没领会。

往上往下dp。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 int n,x,y,num[26][26],d1[26][26],d2[26][26]; 7  8 int dp1(int i,int j) 9 {10     if(d1[i][j]>=0) return d1[i][j];11     return d1[i][j]= ( (i==n)? num[i][j] : ( max(dp1(i+1,j),dp1(i+1,j+1))+num[i][j] ) );12 }13 14 int dp2(int i,int j)15 {16     if(d2[i][j]>=0) return d2[i][j];17     if(i==1) return d2[i][j]=num[i][j];18     int ans=num[i][j]+dp2(i-1,j);19     if(j-1>0) ans=max(ans,num[i][j]+dp2(i-1,j-1));20     return ans;21 }22 23 int main(void)24 {25     cin>>n;26     memset(d1,-1,sizeof(d1));27     memset(d2,-1,sizeof(d2));28     for(int i=1;i<=n;i++)29         for(int j=1;j<=i;j++)30             scanf("%d",&num[i][j]);31     scanf("%d%d",&x,&y);32     printf("%d\n",dp1(x,y)+dp2(x,y)-num[x][y]);33     return 0;34 }

Aguin

题目没什么。代码丑。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 # define X(i) (i/c+((i%c)?1:0)) 6 # define Y(i) ((i%c)?(i%c):c) 7 # define ID(i,j) ((i-1)*c+j) 8 int dp[10001],map[10001]; 9 10 struct node11 {12     int id,h;13 } G[10001];14 15 bool cmp(node a,node b)16 {17     return a.h>b.h;18 }19 20 int main(void)21 {22     int r,c; cin>>r>>c;23     for(int i=1;i<=r*c;i++)24     {25         scanf("%d",&G[i].h);26         G[i].id=i;27     }28     sort(G+1,G+r*c+1,cmp);29     for(int i=1;i<=r*c;i++) map[G[i].id]=i;30     int ans=0;31     for(int i=1;i<=r*c;i++)32     {33         int no=G[i].id,x=X(no),y=Y(no),H=G[i].h;34         dp[no]=1;35         if(x>1&&G[map[ID(x-1,y)]].h>H) dp[no]=max(dp[no],dp[G[map[ID(x-1,y)]].id]+1);36         if(y>1&&G[map[ID(x,y-1)]].h>H) dp[no]=max(dp[no],dp[G[map[ID(x,y-1)]].id]+1);37         if(x
         
          H) dp[no]=max(dp[no],dp[G[map[ID(x+1,y)]].id]+1);38         if(y
          
           H) dp[no]=max(dp[no],dp[G[map[ID(x,y+1)]].id]+1);39         ans=max(ans,dp[no]);40     }41     printf("%d\n",ans);42     return 0;43 }

Aguin

6.24

HDU 1231

1 # include 
      
        2 # include 
       
         3 using namespace std; 4 int num[10005],dp[10005],head[10005]; 5  6 int main(void) 7 { 8     int K; 9     while((scanf("%d",&K))!=EOF&&K)10     {11         for(int i=0;i
        
         0) {dp[i]=dp[i-1]+num[i];head[i]=head[i-1];}15             else {dp[i]=num[i];head[i]=num[i];}16         int sum=-1,pos;17         for(int i=0;i
         
          sum) {sum=dp[i];pos=i;}19         if(sum<0) printf("0 %d %d\n",num[0],num[K-1]);20         else printf("%d %d %d\n",sum,head[pos],num[pos]);21     }22     return 0;23 }

Aguin

LCS

想不出来阿阿阿阿阿阿阿阿阿阿阿。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 char a[1005],b[1005]; 7 int F[1005][1005]; 8  9 int dp(int i,int j)10 {11     if(F[i][j]>=0) return F[i][j];12     if(i==0||j==0) return F[i][j]=0;13     if(a[i]==b[j]) return F[i][j]=dp(i-1,j-1)+1;14     return F[i][j]=max(dp(i,j-1),dp(i-1,j));15 }16 17 int main(void)18 {19     int N;cin>>N;20     while(N--)21     {22         memset(F,-1,sizeof(F));23         scanf("%s %s",a+1,b+1);24         printf("%d\n",dp(strlen(a+1),strlen(b+1)));25     }26     return 0;27 }

Aguin

POJ 1050

二维最大连续子列。

枚举了列的范围。在行求最大连续子列。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 int sum[105][105]={
    0},dp[105][105][105]; 6  7 int main(void) 8 { 9     int N;10     while(cin>>N)11     {12         for(int i=1;i<=N;i++)13             for(int j=1;j<=N;j++)14             {15                 int x; scanf("%d",&x);16                 sum[i][j]=x;17                 if(j) sum[i][j]+=sum[i][j-1];18             }19         int ans=-2147483647;20         for(int i=1;i<=N;i++)21             for(int j=i;j<=N;j++)22                 for(int k=1;k<=N;k++)23                 {24                     if(i&&dp[i][j][k-1]>0) dp[i][j][k]=dp[i][j][k-1]+sum[k][j]-sum[k][i-1];25                     else dp[i][j][k]=sum[k][j]-sum[k][i-1];26                     ans=max(ans,dp[i][j][k]);27                 }28         printf("%d\n",ans);29     }30     return 0;31 }

Aguin

6.25

一个题没写完。明日补。

6.26

看DP的时候看见这个。

咦？这难道不是线段树吗- -

然而并没有update。于是可有更高效的算法。

于是发现了解决RMQ问题的ST算法。

之前有看见过ST。以为是什么高大上就没有看。

看了一下发现和线段树的二分一样。就像每个点下面有一个不能update的树。

预处理的时候至下而上的操作是DP。然后就可以O(1)query拉。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 # define maxn 100000+5 7 int num[maxn],MAX[maxn][20],MIN[maxn][20]; 8  9 int main(void)10 {11     int N,Q;cin>>N>>Q;12     for(int i=1;i<=N;i++)13     {14         scanf("%d",num+i);15         MAX[i][0]=MIN[i][0]=num[i];    16     }17     for(int j=1;j<20;j++)18         for(int i=1;i<=N;i++)19             if(i+(1<
          
           <=N)20             {21                 MAX[i][j]=max(MAX[i][j-1],MAX[i+(1<

Aguin

6.27

HDU 5266

上上周BC一个题。LCA+ST。学了ST之后立马翻出了这题。

中间还用到了dfs序。感觉处理的不是很棒。代码也丑。

时限开的6s。2s跑完还行吧。1次AC开心。

1 # pragma comment(linker, "/STACK:1024000000,1024000000") 2 # include 
      
        3 # include 
       
         4 # include 
        
          5 # include 
         
           6 # include 
          
            7 # include 
           
             8 using namespace std; 9 # define maxn 300000+1010 # define CLR(x) memset(x,0,sizeof(x))11 int t,pa[maxn],ans[maxn],MAX[maxn][20],MIN[maxn][20];12 bool vis[maxn];13 vector 
            
              vec[maxn];14 vector < pair
             
               > query[maxn];15 16 int fa(int x)17 {18 return pa[x]==x?x:pa[x]=fa(pa[x]);19 }20 21 struct node22 {23 int no,time;24 } T1[maxn],T2[maxn];25 26 void dfs(int i)27 {28 T1[i].no=i; T1[i].time=++t;29 MAX[i][0]=MIN[i][0]=t;30 for(int j=0;j
              
               T2[x].time)44 {45 LCA(T2[vec[x][i]].no);46 pa[T2[vec[x][i]].no]=x;47 }48 vis[x]=1;49 for(int i=0;i
               
                >n)61 {62 CLR(vis); CLR(T1);63 for(int i=1;i<=n;i++)64 {65 pa[i]=i;66 vec[i].clear();67 query[i].clear();68 }69 for(int i=0;i