---恢复内容开始---
很失败的一次，主要是被PI的精度卡了？！
小雨的矩阵
dfs
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<algorithm> #include<vector> #include<set> using namespace std; typedef long long ll; #define PI 3.1415927 #define M(a) memset(a,0,sizeof(a)) const int INF=0x3f3f3f3f; int maze[55][55]; int num1[3500]; int n; bool test(int x,int y) { if(x>=n||y>=n) return 0; return 1; } void dfs(int x,int y,int ans) { if(x==n-1&&y==n-1) { num1[ans]++; return; } if(test(x,y)) { dfs(x+1,y,ans+maze[x+1][y]); dfs(x,y+1,ans+maze[x][y+1]); } return; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) scanf("%d",&maze[i][j]); } dfs(0,0,maze[0][0]); int ans=0; for(int i=0;i<3500;i++) { if(num1[i]) { ans++; } } printf("%d ",ans); return 0; }
bfs
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; #define PI 3.1415927 #define M(a) memset(a,0,sizeof(a)) const int INF=0x3f3f3f3f; int maze[55][55]; int num1[3500]; int dir[2][2]={{0,1},{1,0}}; int vis[55][55]; int n; struct node{ int x,y,vau; node(int xx,int yy,int vv) { x=xx; y=yy; vau=vv; } }; bool test(int x,int y) { if(x>=n||y>=n) { return 0; } return 1; } void bfs(int x,int y,int v1) { queue<node> q; q.push(node(x,y,v1)); while(!q.empty()) { node top=q.front(); q.pop(); vis[x][y]=1; if(top.x==n-1&&top.y==n-1) { num1[top.vau]++; } for(int i=0;i<2;i++) { int tx=top.x+dir[0][i]; int ty=top.y+dir[1][i]; int tv=top.vau+maze[tx][ty]; if(test(tx,ty)) { q.push(node(tx,ty,tv)); vis[tx][ty]=1; } } } return; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) scanf("%d",&maze[i][j]); } bfs(0,0,maze[0][0]); int ans=0; for(int i=0;i<3500;i++) { if(num1[i]) { ans++; } } printf("%d ",ans); return 0; }
这是大佬的方法：
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int a[100][100],f[10][10][1000]; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); f[1][1][a[1][1]]=1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (i==1&&j==1) continue; for (int k=a[i][j];k<=800;k++) if (f[i-1][j][k-a[i][j]]||f[i][j-1][k-a[i][j]]) f[i][j][k]=1; } int ans=0; for (int i=0;i<=800;i++) if (f[n][n][i]) ans++; printf("%d ",ans); }
D-小阳买水果
大概思想是，从左边开始，一边输入一边二分查找
这是大佬代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int MAX = 1e6*2+10; ll a[MAX]; ll x,w; int ans; int main() { int n; scanf("%d",&n); for (int i = 1; i <= n;i++){ scanf("%lld",&x); w+=x; a[i]=min(a[i-1],w); if(w>0){//总和大于0，特判 ans=max(ans,i);//不需要减1 continue; } int l=1,r=i; while(l<=r){//二分找左边最小值 int mid=(l+r)>>1; if(a[mid]<w) r=mid-1; else l=mid+1; } ans=max(ans,i-r-1);//需要减1，自己推一下，不好解释~~（大体就是找到右边小于0的那一块，多了一个负值，把多的那个值去掉，右边就是大于0的，当然那个负值在右边那一块的最左边） } printf("%lld ",ans); return 0; }
---恢复内容结束---