P2853 [USACO06DEC]牛的野餐Cow Picnic
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,k,p[10000],can[10000]; 4 int w[1000+15][1000+15]; 5 bool vis[10000]; 6 7 void dfs(int pre) 8 { 9 for(int j=1;j<=n;j++) 10 { 11 if(w[pre][j]&&!vis[j]) 12 { 13 vis[j]=1; can[j]++; 14 dfs(j); 15 } 16 } 17 } 18 19 int main() 20 { 21 scanf("%d%d%d",&k,&n,&m); 22 for(int i=1;i<=k;i++) scanf("%d",&p[i]); 23 for(int i=1;i<=m;i++) 24 { 25 int x,y; 26 scanf("%d%d",&x,&y); 27 w[x][y]=1; 28 } 29 for(int i=1;i<=n;i++) w[i][i]=1; 30 for(int i=1;i<=k;i++) 31 { 32 memset(vis,0,sizeof(vis)); 33 dfs(p[i]); 34 } 35 36 int ans=0; 37 for(int i=1;i<=n;i++) if(can[i]==k) ans++; 38 printf("%d ",ans); 39 return 0; 40 }
P1451 求细胞数量
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define maxn 100000 4 int n,m,ma[300][300],ans; 5 bool vis[300][300]; 6 int dx[4]={0,0,1,-1}; 7 int dy[4]={1,-1,0,0}; 8 char s[300][300]; 9 10 void dfs(int x,int y) 11 { 12 if(x<0||y<0||x>=n||y>=m||vis[x][y]) return ; 13 vis[x][y]=true; 14 for(int i=0;i<4;i++) 15 if(s[x+dx[i]][y+dy[i]]!='0') 16 dfs(x+dx[i],y+dy[i]); 17 } 18 19 int main() 20 { 21 scanf("%d%d",&n,&m); 22 for(int i=0;i<n;i++) cin>>s[i]; 23 for(int i=0;i<n;i++) 24 for(int j=0;j<m;j++) 25 if(!vis[i][j]&&s[i][j]!='0') ans++,dfs(i,j); 26 printf("%d ",ans); 27 return 0; 28 }
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 #define inf 1000000 9 int n,num; 10 double ans=inf*1.0,x[10000],y[10000],dis[100][100]; 11 bool vis[100000]; 12 13 void dfs(double now,int num,int prex) 14 { 15 if(now>ans) return ; 16 if(num==n) 17 { 18 ans=min(ans,now); 19 return ; 20 } 21 for(int i=1;i<=n;i++) 22 { 23 if(!vis[i]) 24 { 25 vis[i]=1; 26 dfs(dis[prex][i]+now,num+1,i); 27 vis[i]=0; 28 } 29 } 30 31 } 32 33 int main() 34 { 35 scanf("%d",&n); 36 for(int i=1;i<=n;i++) 37 scanf("%lf%lf",&x[i],&y[i]); 38 for(int i=0;i<=n;i++) 39 for(int j=0;j<=n;j++) 40 if(i!=j) dis[i][j]=sqrt(pow(x[j]-x[i],2)+pow(y[j]-y[i],2)); 41 dfs(0,0,0); 42 printf("%.2lf ",ans); 43 return 0; 44 }
P1162 填涂颜色
搜边界，遇到 1 return
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,ma[100][100]; 4 int dx[4]={0,0,1,-1}; 5 int dy[4]={1,-1,0,0}; 6 bool vis[100][100]; 7 8 void dfs(int now_x,int now_y) 9 { 10 if(ma[now_x][now_y]==1) return ; 11 vis[now_x][now_y]=true; 12 for(int i=0;i<4;i++) 13 { 14 int xx=now_x+dx[i],yy=now_y+dy[i]; 15 if(xx>0&&xx<=n&&yy>0&&yy<=n&&ma[xx][yy]!=1&&!vis[xx][yy]) 16 dfs(xx,yy); 17 } 18 } 19 20 int main() 21 { 22 scanf("%d",&n); 23 for(int i=1;i<=n;i++) 24 for(int j=1;j<=n;j++) 25 scanf("%d",&ma[i][j]); 26 for(int i=1;i<=n;i++) 27 dfs(i,1),dfs(1,i),dfs(i,n),dfs(n,i); 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=n;j++) 30 if(ma[i][j]==1) ma[i][j]=-1; 31 // printf(" "); 32 for(int i=1;i<=n;i++) 33 { 34 for(int j=1;j<=n;j++) 35 { 36 if(!vis[i][j]) 37 printf("%d ",ma[i][j]+2); 38 else printf("%d ",ma[i][j]); 39 } 40 41 printf(" "); 42 } 43 return 0; 44 }
P2800 又上锁妖塔
第k层可以由k-2层或k-1层跳上来，或者从k-1层爬上来，但是因为每跳一次必须要爬一次
所以转移方程为 dp[i]=min(dp[i-3]+h[i-2],min(dp[i-2]+h[i-1],dp[i-1]+h[i]))
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,h[1000000+15],dp[1000000+15]; 4 int main() 5 { 6 scanf("%d",&n); 7 for(int i=1;i<=n;i++) scanf("%d",&h[i]); 8 dp[1]=dp[2]=0; 9 for(int i=3;i<=n;i++) 10 dp[i]=min(dp[i-3]+h[i-2],min(dp[i-2]+h[i-1],dp[i-1]+h[i])); 11 printf("%d",dp[n]); 12 }
P1852 奇怪的字符串
最长公共子序列
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,a[1000000],b[1000000],dp[3000][3000]; 4 string s1,s2; 5 int main() 6 { 7 cin>>s1>>s2; 8 n=s1.length(),m=s2.length(); 9 for(int i=0;i<n;i++) a[i+1]=s1[i]-'0'; 10 for(int i=0;i<m;i++) b[i+1]=s2[i]-'0'; 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=m;j++) 13 { 14 if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); 15 if(a[i]!=b[j]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 16 } 17 printf("%d",dp[n][m]); 18 return 0; 19 }