Round Subset(codeforces 837D)

3540 단어 동적 계획
제목 링크:[http://codeforces.com/problemset/problem/837/D]
분석:
끝 이 0 인 것 은 분명히 2*5 에서 얻 은 것 이다.각각 ai a i 를 분해 하여 2 와 5 의 수량 을 얻 을 수 있 습 니 다.대략 계산 해 보면 2 의 수량 은 최대 12800 개,5 의 수량 은 최대 6000 개 이기 때문에 5 의 수량 을 가방 용량 으로 하여 최대 몇 개의 2 를 계산 할 수 있 습 니까?방정식
dp[i][k][j]=max{dp[i−1][k−1][j−x[i]]+y[i]} d p [ i ] [ k ] [ j ] = m a x { d p [ i − 1 ] [ k − 1 ] [ j − x [ i ] ] + y [ i ] }
그 중
1≤i≤n,1≤k≤m 1 ≤ i ≤ n , 1 ≤ k ≤ m ,
xi,yi x i,y i 는 각각 1 등 이다.
i 개 수 5 의 수량 과 2 의 수량
전이 방정식 에 대한 강 차원.
코드:
#include
#include
#include
#include
using namespace std;

#define ll long long

const ll INF = 0x7ffffff;
int n,m,sum,x[220],y[220];
ll a,ans,f[220][6000];

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=0;iscanf("%I64d",&a);
        ll now = a;
        while (now % 5 == 0)
        {
            x[i]++;
            now /= 5;
        }
        sum += x[i];
        now = a;
        while (now % 2 == 0)
        {
            y[i]++;
            now >>= 1;
        }
    }
    for (int k=0;k<=m;k++)
        for (int j=0;j<6000;j++) f[k][j] = -INF;
    f[0][0] = 0;
    for (int i=0;ifor (int k=m;k>0;k--)
            for (int j=x[i];j<=sum;j++)
                f[k][j] = max(f[k][j],f[k-1][j-x[i]]+y[i]);
    }
    for (int j=0;j<=sum;j++)
    {
        ll now = f[m][j];
        if (j < now) now = j;
        ans = max(now,ans);
    }
    printf("%I64d
"
,ans); return 0; }

좋은 웹페이지 즐겨찾기