これは良問だと思った。 これを機にダイクストラ法の理解が一層深まった気がする。 解説 まず、下のコードではdpテーブルはdとおいて、d[0][i]に普通のダイクストラ法をやっていく。その後にmin(~,~)で割引券を使った時と使ってない時を判定して、最短経路を…

解説 サンプルセット見た感じだと、多分縮小の問題だと思うのでそのまま実装 #include <iostream> #include <cstdio> #include <cmath> using namespace std; int f(double a, double b){ return (int)(b/a*100); } int main(){ int l,r; double a,b,c,d; while(cin >> a >> b >> c >></cmath></cstdio></iostream>…