RCC 2014 ウォームアップ (ディビジョン 2)Cunning Gena_html/css_WEB-ITnose

質問リンク

質問の意味:
n: 人数、m: 質問数、b: 各モニターの価格を入力します
次に、各人について、x: 必要なお金、k を少なくともモニターの数を入力します必須、m : 会議の議題
次の行に会議の議題を入力します
すべての議題が含まれ、お金が最小になるように何人かを選択します (各人が必要とするお金とモニターのお金)
(1?≤?n?≤?100; 1?≤?m?≤?20; 1?≤?b?≤?109), (1?≤?xi?≤?109; 1?≤?ki? ≤?109; 1?≤?mi?≤?m)

分析:
質問内のデータ量が比較的少ない場合は、明らかに状態圧力 DP を使用して実行できます。現在のモニターのステータスを追加するだけです。 。ただし、重要な点は、問題の k が比較的大きいため、この次元が追加されると、DP は明らかに不可能になるということです。基本的には DP の原則に準拠しており、モニターの数だけが一致していないため、この状態に対処する方法を検討します。この状態要件は少なくとも、ある時点で選択されたすべての人の k の最大値を考慮すると、最後の k が最大であるため、他の人は k の値を考慮する必要がありません。次に、すべての人を k で並べ替えることができます。0 から i-1 までは通常の DP です (i 番目の人に関しては、k は考慮されません)。 i と比較できる状態を見つけます。人間の質問の合計はすべての値に達します (すべての質問をカバーします)。ただし、この時点で k*percost を追加できます。
繰り返しになりますが、この問題は実際には、各人物を行、トピックを列とする DLX として考えることができます。ただし問題は、最小コストと k の両方を計算する必要があることです。これはやはり繰り返しカバレッジです。枝刈り効率は高くなく、この量のデータではタイムアウトしますが、これも方向性です。

キーポイント:
鍵となるのは、状態圧力 DP によって問題を解決できるように、大きな次元を扱うことです
INF の初期化に注意してください

const LL INF = 1100000000000000000;const int MAXN = 110;struct Node{    int cost, Min, n;    int operator< (const Node& a) const    {        return Min < a.Min;    }} ipt[MAXN];LL dp[1100000];int main(){//    freopen("in.txt", "r", stdin);    int people, problem, percost;    while (~RIII(people, problem, percost))    {        int all = (1 << problem) - 1;        FE(i, 1, all) dp[i] = INF;        dp[0] = 0;        REP(i, people)        {            RII(ipt[i].cost, ipt[i].Min);            int n, t, v = 0;            RI(n);            REP(j, n)            {                RI(t);                v |= (1 << (t - 1));            }            ipt[i].n = v;        }        sort(ipt, ipt + people);        LL ans = INF;        REP(i, people)        {            FE(j, 0, all)            {                if ((ipt[i].n | j) == all)                {                    ans = min(ans, dp[j] + ipt[i].cost + (LL)percost * ipt[i].Min);                }            }            FED(j, all, 0)            {                int nxt = j | ipt[i].n;                dp[nxt] = min(dp[nxt], dp[j] + ipt[i].cost);            }        }        if (ans != INF)            cout << ans << endl;        else            puts("-1");    }    return 0;}