首页 > 代码库 > codeforces349B - Color the Fence 贪心+DP

codeforces349B - Color the Fence 贪心+DP

2024-07-13 22:00:50   221人阅读

题意：1-9每个字母需要消耗ai升油漆，问你用油漆最多刻意画多大的数字

解题思路：

首先我们要贪心，可以知道我最优是先使我们位数尽可能长，然后才是就是位数长的情况下使得从最高位开始尽可能大。所以要取满足最长位最小的那个数，方便我们DP

解题代码：

 1 // File Name: 349b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月24日 星期四 21时40分13秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 27 int a[10];28 int main(){29    int n;30    scanf("%d",&n);31    for(int i = 1;i <= 9 ;i ++)32         scanf("%d",&a[i]);33    int maxn = -1; 34    int num; 35    for(int i =9; i >= 1 ;i--)36        {37           int t = n/a[i];38           if(t > maxn ||(t == maxn && a[i] < a[num]))39           {40              maxn = t; 41              num = i ; 42           }43        }44    if(maxn == 0 )45    {46       printf("-1\n");47       return 0 ;48    }49    int k = 0 ;50    n = n % a[num];51    while(n)52    {53      int ok = 0 ; 54      for(int i = 9;i >= num+1;i --)55      {56         if(a[i] - a[num] <= n )57         {58            n -= (a[i]-a[num]);59            printf("%d",i);60            ok = 1; 61            k ++ ;62            break;63         }64      }65      if(ok == 0 )66          break;67    }68    for(int i = 1;i <= maxn - k;i ++)69        printf("%d",num);70    printf("\n");71 return 0;72 }
View Code


联系
我们