其实比较简单，主要是比较的方法以前没看过吧
要学会知识迁移啊！
#include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1010; const int INF=0x3fffffff; double a,b,l; int gcd(int x,int y){ if(x%y==0) return y; else return gcd(y,x%y); } int main(){ cin>>a>>b>>l; //其实很简单，别想复杂了 int suma=l,sumb=1; //注意初值 for(int i=1;i<=l;i++){ for(int j=1;j<=l;j++){ if(gcd(i,j)==1&&(i*b>=j*a)&&(i*sumb T3】螺旋矩阵 #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1010; const int INF=0x3fffffff; int n,x,y; //又是一道找规律的题。。。我哭 //肯定不能直接构造这个矩阵，肯定会超时 //所以找到特殊的方法，特殊点 //看了题解发现是用层次来找的,分层讨论 //可以分为上面，左边，右边，下面 //比如坐标i,j，他的层次就在于min(i,j,n-i+1,n-j+1) void dfs(int n,int x,int y){ int layer=min(x,min(y,min(n-x+1,n-y+1))); int fir=n*n-(n-2*layer+2)*(n-2*layer+2)+1; //这个是第一个 if(layer==x){ //如果在上面，就直接往右边走就可以可 cout<>n>>x>>y; dfs(n,x,y); return 0; } T4】子矩阵 这道题还有点复杂 首先选行：dfs选择所有的组合 然后在选定的行里面选择最好的列组合 这里比较难 就是怎么选，因为可以不是连续的，所以要记录所有的行之间相差的状况 #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1010; const int INF=0x3fffffff; int n,m,r,c; int res=INF; int t[20],t1[20][20]; int a[20][20]; int v[20]; int f[20]; int temp[20]; //一开始搜索一种行的组合方法，然后就在这选择的行里面，选择得到和最小的列的组合，得到最小的值 //循环各种搜索得到的组合，然后dp就可以 int dp(){ memset(t,0,sizeof(t)); memset(t1,0,sizeof(t1)); for(int i=1;i<=m;i++){ for(int j=1;j=i;j--){ //遍历用j,k f[j]=INF; for(int k=j-1;k>=i-1;k--) f[j]=min(f[j],f[k]+t1[k][j]); f[j]+=t[j]; } } int ans=INF; for(int i=c;i<=m;i++){ if(ans>f[i]){ ans=f[i]; //for(int j=1;j<=m;j++) temp[j]=f[j]; } } return ans; } void findd(int i,int step){ if(step==r){ res=min(res,dp()); return; } for(int j=i;j<=n-r+step+1;j++){ v[++v[0]]=j; //存储当前找到的列号 findd(j+1,step+1); //找到下一个组合 v[v[0]--]=0; //回溯 } } int main(){ scanf("%d %d %d %d",&n,&m,&r,&c); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } findd(1,0); printf("%d\n",res); return 0; }
#include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1010; const int INF=0x3fffffff; int n,x,y; //又是一道找规律的题。。。我哭 //肯定不能直接构造这个矩阵，肯定会超时 //所以找到特殊的方法，特殊点 //看了题解发现是用层次来找的,分层讨论 //可以分为上面，左边，右边，下面 //比如坐标i,j，他的层次就在于min(i,j,n-i+1,n-j+1) void dfs(int n,int x,int y){ int layer=min(x,min(y,min(n-x+1,n-y+1))); int fir=n*n-(n-2*layer+2)*(n-2*layer+2)+1; //这个是第一个 if(layer==x){ //如果在上面，就直接往右边走就可以可 cout<>n>>x>>y; dfs(n,x,y); return 0; }
这道题还有点复杂
首先选行：dfs选择所有的组合
然后在选定的行里面选择最好的列组合
这里比较难
就是怎么选，因为可以不是连续的，所以要记录所有的行之间相差的状况
#include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1010; const int INF=0x3fffffff; int n,m,r,c; int res=INF; int t[20],t1[20][20]; int a[20][20]; int v[20]; int f[20]; int temp[20]; //一开始搜索一种行的组合方法，然后就在这选择的行里面，选择得到和最小的列的组合，得到最小的值 //循环各种搜索得到的组合，然后dp就可以 int dp(){ memset(t,0,sizeof(t)); memset(t1,0,sizeof(t1)); for(int i=1;i<=m;i++){ for(int j=1;j=i;j--){ //遍历用j,k f[j]=INF; for(int k=j-1;k>=i-1;k--) f[j]=min(f[j],f[k]+t1[k][j]); f[j]+=t[j]; } } int ans=INF; for(int i=c;i<=m;i++){ if(ans>f[i]){ ans=f[i]; //for(int j=1;j<=m;j++) temp[j]=f[j]; } } return ans; } void findd(int i,int step){ if(step==r){ res=min(res,dp()); return; } for(int j=i;j<=n-r+step+1;j++){ v[++v[0]]=j; //存储当前找到的列号 findd(j+1,step+1); //找到下一个组合 v[v[0]--]=0; //回溯 } } int main(){ scanf("%d %d %d %d",&n,&m,&r,&c); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } findd(1,0); printf("%d\n",res); return 0; }