CF D. Kefa and Dishes(상태 이동 dp)

3961 단어 dpCodeforces
제목:
혼자 가서 주문해. n종에서 m종.모든 요리는 만족도가 있고 그는 k개의 규칙을 제정했다. 만약에 a가 b 전에 먹으면 추가로 만족도를 얻을 수 있다.최대 만족도를 구하다.
아이디어:
문제의 규모가 크지 않기 때문에 (1 ≤ m≤ n ≤ 18, 0 ≤ k≤ n * (n - 1)) 상태이전 dp를 뚜렷하게 사용해야 하는데 무슨 소용이 있습니까?하나의 상태가 필요하다면 st는 요리의 선택 상태를 표시하고 i는 i종 요리를 끝으로 하는 최대치를 표시하며 st의 모든 상황을 두루 돌아다니며 dp[st][i]를 구한다.
#include 
#include 
#include 

using namespace std;

const int MAXN = 1<<18;
typedef long long LL;

int n,m,k;
LL dp[MAXN+10][21];
int bom[30][30];
int a[30];

int Cnt(int st)
{
    int res = 0;
    for(int i = 0;i < n; i++) {
        if(st&(1<return res;
}

int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < n; i++)
        scanf("%d",&a[i]);
    for(int i = 0;i < k; i++) {
        int s,e,v;
        scanf("%d%d%d",&s,&e,&v);
        s--,e--;
        bom[s][e] = v;
    }
    int maxn = 1<0;
    for(int st = 0;st < maxn; st++) {
        for(int i = 0;i < n; i++) {
            if(st&(1<int flag = false;
                for(int j = 0;j < n; j++) {
                    if(j != i && st&(1<true;
                        dp[st][i] = max(dp[st][i],dp[st^(1<if(!flag) {
                    dp[st][i] = a[i];
                }
            }
            if(Cnt(st) == m) {
                ans = max(ans,dp[st][i]);
            }
        }
    }
    cout<return 0;
}
JSX 초보자 기초
ZFS에 Manjaro 설치

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage