洛谷 UVA12563 Jin Ge Jin Qu hao 题解

这道题其实是一道01背包的变形题，主要思路如下：在不把剩余时间用光的前提下（剩余时间>0），尽可能的多唱歌。于是我们可以用dp[i]表示的是到当前i秒时，最多可以唱多少歌。

状态转换方程：dp[k]=max(dp[k],dp[k-yy]+1);最后输出可以唱多少歌。

 #include<bits/stdc++.h>

 using namespace std;

 int n,t,m,yy;

 int dp[];

 int main()

 {

     cin>>n;

     for(int i=;i<=n;i++)

     {

         memset(dp,0x8f,sizeof(dp));

         cin>>m>>t;

         dp[]=;

         for(int j=;j<=m;j++)

         {

             cin>>yy;

             for(int k=t-;k>=yy;k--)

             {

                 dp[k]=max(dp[k],dp[k-yy]+);

             }

         }

         int ans;

         for(int j=ans=t-;j>=;j--)

         {

             if(dp[j]>dp[ans])ans=j;

         }

         cout<<"Case"<<" "<<i<<":"<<" "<<dp[ans]+<<" "<<ans+<<endl;

     }

     return ;

 }
请各位大佬斧正（反正我不认识斧正是什么意思）

巴特西

洛谷 UVA12563 Jin Ge Jin Qu hao 题解

最新文章

热门文章