[bzoj 1024][SCOI 2009]생일 축하합니다[폭력]

2546 단어 [폭력]
[제목 링크]http://www.lydsy.com/JudgeOnline/problem.php?id=1024 [문제 풀이]폭력 은 칼 마다 가로로 자 르 느 냐 세로 로 자 르 느 냐 양쪽 의 덩어리 를 매 거 한다.복잡 도 분석:g[i]g[i]를 n=i n=i 로 설정 할 때의 복잡 도.그래서 g[i]=1(i=1)g[i]=1(i=1)g[i]=2∗∑i−1j=1(g[j]+g[i−j])+1(i≥2)g[i]=2∗∑j=1 i−1(g[j]+g[i−j])+1(i≥2)정리 후 g[i]=5i−1 g[i]=5 i−1 이 므 로 복잡 도 는 O(5n 5 n)이다.
/* --------------
    user Vanisher
    problem bzoj-1024
----------------*/
# include 
# define    ll      long long
# define    inf     0x3f3f3f3f
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
double solve(double x, double y, int k){
    if (xif (k==1) return x/y;
    double ans=inf;
    for (int i=1; ireturn ans;
}
int main(){
    int x=read(), y=read(), n=read();
    printf("%.6lf
"
,solve(x,y,n)); return 0; }

좋은 웹페이지 즐겨찾기