共通部分文字列の長さの最大値を求める問題。 1文字後ろを調べ、同じ文字列を重複して調べないようにすると、TLEしないで解けます。 O(n^3)かO(n^2)です。 #include<iostream> #include<string> #include<algorithm> using namespace std; string s,t; int main(){ while(cin>>s>>t){ int </algorithm></string></iostream>…

辺が増えていく最短経路問題。増えた辺を使うと経路が短くなる場合があるので、それを調べます。(増えた辺を使わないで経路が短くなることはない) O(kn^2)です。AOJではギリギリ通せなかったのですが、ワーシャルフロイド法(や、その他の最短路のアルゴリズ…

最大値の伝播で解くのは難しそうだったから、累積和で解きました。 少し枝刈りしましたが遅いです。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int g[10003][10003]; int n,r; int main(){ while(scanf("%d%d",&n,&r),n){ memset(g,0,sizeof(g)); in</algorithm></cstring></cstdio>…

Div1は550を誰かが解かないとノーコン(Div1)になるらしいです(2012/04/15 15:01) 問題見てみたいけど、Div2だと見れないみたいです。practiceに入りました。 Easy(174.03 / 250) 遺伝子の情報が与えられて、1つの家族として考えられるものの中で、最も人数の…