2015.2.7
Bzoj 1044 [HAOI2008]木棍分割
第一问 二分答案[二分的是最大值需求是最小] 判断其可行性 若可行则说明答案将可以小于等于其
第二问 设F[i][j]为到第i段砍(j-1)刀分为j块方案总数
F[i][j]=ΣF[k][j-1] | Sum[i]-Sum[k-1]<=Ans1
又 Sum[i]-Sum[k]<=Ans1 说明 Sum[i-1]-Sum[k]<=Ans1
i 可以借取之前的必定小于它的数字 k 的和 用另外一个数组记录一下即可
2015.2.8
Bzoj 1048 [HAOI2007]分割矩阵
补充数据范围 1<=n,a,b<=10 定义 Dfs (x,y,X,Y,k) 表示 左上角是(x,y) 右下角是(X,Y) 分为 k 个矩阵方差的最小值
因为均方差是方差开根号而平均数是一定的所以方差是可以求出来的
所以均方差的最小就是方差的最小
记忆化搜索即可
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define Rep(i,x,y) for (i=x;i<=y;++i)
#define DL double
const int N = 15 + 1 , M = 15 + 1 , T = 15 + 1 ;
const double Inf = 1E9 ;
DL F[N][M][N][M][T];
int S[N][M],i,k,j,n,m,K,p,q,x;
DL Ave;
DL Dfs(int x,int y,int X,int Y,int p) {
if (p==1) return F[x][y][X][Y][p]=(S[X][Y]-S[x-1][Y]-S[X][y-1]+S[x-1][y-1]-Ave)*(S[X][Y]-S[x-1][Y]-S[X][y-1]+S[x-1][y-1]-Ave);
if (F[x][y][X][Y][p]!=-1) return F[x][y][X][Y][p];
DL P=Inf;
int i,k;
Rep(i,x,X-1) Rep(k,1,p-1) P=min(P,Dfs(x,y,i,Y,k)+Dfs(i+1,y,X,Y,p-k));
Rep(i,y,Y-1) Rep(k,1,p-1) P=min(P,Dfs(x,y,X,i,k)+Dfs(x,i+1,X,Y,p-k));
return F[x][y][X][Y][p]=P;
}
int main() {
cin>>n>>m>>K;
Rep(i,1,n) Rep(j,1,m) Rep(p,1,n)Rep(q,1,m) Rep(k,1,K) F[i][j][p][q][k]=-1;
memset(S,0,sizeof(S));
Rep(i,1,n) Rep(j,1,m) { cin>>x; S[i][j]=S[i-1][j]+S[i][j-1]+x-S[i-1][j-1]; }
Ave=(DL)S[n][m]/(DL)K; //所有矩阵的平均分
Dfs(1,1,n,m,K);
printf("%.2lf\n", sqrt(F[1][1][n][m][K]/(DL)K)); //方差开根号 标准差
return 0;
}
Bzoj 1053 [HAOI2007]反素数ant
G(x)>G(i) 1<=i<=x
如果 G(X) 不为 <=N 最大 那么有 G(X') 最大
如果 X'<X 那么 X 不符
如果 X'>X 那么 X 更佳
所以找约数最多的数 相同的最多取最小
Const A:array[1..9] of Int64=(2,3,5,7,11,13,17,19,23); Var n,Ans,Num:longint; Procedure Dfs(x,p,Lp,T,S:Int64); var i:longint; Begin if (S*(p+1)>Ans)or(S*(p+1)=Ans)and(T<Num) then begin Ans:=S*(p+1); Num:=T; End; //如果约数相同同为最大那么 (x>i) g(x)=g(i) x 不满足要求 i 满足要求 所以是找约数最多的数 相同的取最小值 if (T*A[x]<=n)and(p<Lp) then Dfs(x,p+1,Lp,T*A[x],S); For i:=x+1 to 9 do if T*A[i]<=n then Dfs(i,1,p,T*A[i],S*(p+1)); //到下一个时统计上一个对约数个数的贡献 End; Begin Readln(n); Ans:=0; Num:=-1; Dfs(1,0,10,1,1); writeln(Num); End.
Bzoj 2761 [JLOI2011]不重复数字
判重复 显然Hash即可 使用链表Hash可以做到空间复杂度O(n) 然后注意输出格式和数据范围(负数）
评论 (0)
