【CODE VS】P1695 windows 2013(DP)
918 ワード
この問題はDPで解答することができて、毎回1つの料理を食べてすべて箸あるいはスプーンを使うことしかできなくて、それでは0でスプーンで食べて、1で箸で食べます
f[i][0または1]は、1番目からi番目の料理まで、スプーン(箸)でi番目の料理を食べるのに要する最短時間を表す
箸とスプーンを変えるのに時間がかかるので、前の料理をスプーンで食べるか、箸で食べるかに分けて移動します
すなわち、動的移動方程式は、
f[i][0]=min(f[i-1][0]+a[i],f[i-1][1]+a[i]+c[i]); f[i][1]=min(f[i-1][0]+b[i]+c[i],f[i-1][1]+b[i]);
コード(C+)
f[i][0または1]は、1番目からi番目の料理まで、スプーン(箸)でi番目の料理を食べるのに要する最短時間を表す
箸とスプーンを変えるのに時間がかかるので、前の料理をスプーンで食べるか、箸で食べるかに分けて移動します
すなわち、動的移動方程式は、
f[i][0]=min(f[i-1][0]+a[i],f[i-1][1]+a[i]+c[i]); f[i][1]=min(f[i-1][0]+b[i]+c[i],f[i-1][1]+b[i]);
コード(C+)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=103;
int f[maxn][2],c[maxn],a[maxn],b[maxn],n;
inline int min(int x,int y)
{
return(x