バルーンが落ちてくる位置と時間が与えられる。 台車が運べるバルーンは３つまでである。 全てのバルーンを拾うことができるか。 また、そのときの最小の移動距離は？ もし全てのバルーンを拾うことができなければ 拾うことができない最初のバルーンの番号を…

xy平面上にN個の点が与えられるので、半径1の円を動かして 囲むことができる点の個数の最大値を求める問題。 ２つの点を円周上にもつ円が最大値の候補になる。 N個の点の中から２点を決めて、その2点を円周上にもつ円を挙げ 囲まれている点の数を数えた。２…

各三角形の頂点nails[A][B]の値をX+1として、一番上の列から順に nails[i][j]=max(nails[i][j],nails[i-1][j-1]-1,nails[i-1][j]-1) を計算して、値が0より大きい場所の個数を数えた。 #include<iostream> #include<algorithm> using namespace std; short max(int a,int b){ retu</algorithm></iostream>…

0 から 100 の数字から異なる n 個の数を取り出して 合計が s となる組み合わせの数を求める問題。 動的計画法で解いた。 dp[取り出す個数][合計]:=組み合わせの数 #include <iostream> using namespace std; long long n,s,dp[11][1001]; int main(void){ dp[0][0] = </iostream>…

ビットDPで解いた。 dp[ビート音の数][ボタンの押し方]:=得点の最大値立っているビットの数を数える関数countは http://tak5219.seesaa.net/article/7042181.html を参考にした。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[30],b[30],dp[31][1<</cstring></algorithm></iostream>…

多角形の頂点の個数と頂点座標が時計回りに与えられるので 多角形の面積を求める問題。http://www004.upp.so-net.ne.jp/s_honma/urawaza/area2.htm ↑を参考に多角形の面積を求める関数を実装した。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<cstdio> #define cu</cstdio></vector></iostream></algorithm></cmath>…

DAGが与えられるので、最長経路を求める問題。 ただしノードPで作業を開始するためには Pまでの最長日数が経っている必要がある。トポロジカルソートしてからDPした。 dp[i]:=結合点iまでの最長日数 #include<iostream> #include<algorithm> #include<vector> #define INF 100000000 using</vector></algorithm></iostream>…