題目大意： 用一張有余額為m的飯卡去打飯，有n種不同價(jià)格的菜，若飯卡余額低于5元?jiǎng)t不能打飯，打飯后余額允許為負(fù)，求余額最低為多少
大致思路： 需要注意的是飯卡余額不能低于5元，所以需要可變范圍要小于等于m-5。由于菜的順序?qū)^(guò)程沒(méi)有影響，所以sort后將價(jià)格最大的菜單獨(dú)拿出來(lái)，在n-1種菜中進(jìn)行動(dòng)態(tài)規(guī)劃。
C++：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn=1010;int c[maxn],dp[maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ if(n==0) break; memset(dp,0,sizeof(dp)); int i,j; for(i=0;i<n;i++) scanf("%d",&c[i]); sort(c,c+n); int cost; scanf("%d",&cost); if(cost>=5){ for(i=0;i<n-1;i++) //將c[n-1]單獨(dú)拿出來(lái) for(j=cost-5;j>=c[i];j--) dp[j]=max(dp[j],dp[j-c[i]]+c[i]);新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
