首页 > 代码库 > TYVJ1195

TYVJ1195

2024-07-19 06:56:12   217人阅读

又是水DP
设dp[i][0] 用勺子吃完第i个菜需要的最小时间
dp[i][1] 用筷子吃完第i个菜需要的最大时间
DP目标min(dp[n][0],dp[n][1])

状态转移：

dp[i][0] = min(dp[i-1][0]+a,dp[i-1][1]+a+c);
dp[i][1] = min(dp[i-1][0]+b+c,dp[i-1][1]+a);

初始条件：
dp[1][0] = a+c;
dp[1][1] = b;

这题可以作为初学者理解DP的很好的例题

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 105; 7  8 int dp[maxn][2]; 9 10 int main()11 {12     //freopen("in.txt","r",stdin);13     int n,a,b,c;14     cin>>n;15     cin>>a>>b>>c;16     dp[1][0] = a+c;17     dp[1][1] = b;18     for(int i = 2;i<=n;++i)19     {20 21         cin>>a>>b>>c;22         dp[i][0] = min(dp[i-1][0]+a,dp[i-1][1]+a+c);23         dp[i][1] = min(dp[i-1][0]+b+c,dp[i-1][1]+b);24     }25     printf("%d\n",min(dp[n][1],dp[n][0]));26     return 0;27 }

 

TYVJ1195


联系
我们