专栏首页算法修养HOJ 2317 Pimp My Ride(状态压缩DP)

HOJ 2317 Pimp My Ride(状态压缩DP)

Pimp My Ride My Tags (Edit) Source : TUD 2005 Time limit : 3 sec Memory limit : 64 M Submitted : 63, Accepted : 34 Today, there are quite a few cars, motorcycles, trucks and other vehicles out there on the streets that would seriously need some refurbishment. You have taken on this job, ripping off a few dollars from a major TV station along the way. Of course, there’s a lot of work to do, and you have decided that it’s getting too much. Therefore you want to have the various jobs like painting, interior decoration and so on done by garages. Unfortunately, those garages are very specialized, so you need different garages for different jobs. More so, they tend to charge you the more the better the overall appearance of the car is. That is, a painter might charge more for a car whose interior is all leather. As those “surcharges” depend on what job is done and which jobs have been done before, you are currently trying to save money by finding an optimal order for those jobs. Problem Individual jobs are numbered 1 through n. Given the base price p for each job and a surcharge s (in USs for job i, if and only if job j was completed before, you are to compute the minimum total costs needed to finish all jobs. Input The first line contains the number of scenarios. For each scenario, an integer number of jobs n, 1 <= n <= 14, is given. Then follow n lines, each containing exactly n integers. The i-th line contains the surcharges that have to be paid in garage number i for the i-th job and the base price for job i. More precisely, on the i-th line, the i-th integer is the base price for job i and the j-th integer (j != i) is the surcharge for job i that applies if job j has been done before. The prices will be non-negative integers smaller than or equal to 100000. Output The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line: “You have officially been pimped for only p” with p being the minimum total price. Terminate the output for the scenario with a blank line.   Sample Input   2   2   10 10   9000 10   3   14 23 0   0 14 0   1000 9500 14   Sample Output   Scenario #1:   You have officially been pimped for only30

Scenario #2: You have officially been pimped for only $42

注意题目:每次做一个job都要把之前做过的所有job额外的费用加上

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 100000000
int dp[1<<15][15];
int a[15][15];
int ans;
int n;
int main()
{
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        int state=(1<<n)-1;
        for(int i=0;i<=state;i++)
            for(int j=0;j<n;j++)
                dp[i][j]=MAX;
        for(int i=0;i<n;i++)
            dp[1<<i][i]=a[i][i];
        for(int i=1;i<=state;i++)
        {
            for(int j=0;j<n;j++)
            {
                if((1<<j)&i)
                {
                    int num=a[j][j];
                    for(int k=0;k<n;k++)
                    {
                        if(k!=j&&((1<<k)&i))
                            num+=a[j][k];
                    }
                    for(int p=0;p<n;p++)
                    {
                        if(p!=j&&((1<<p)&i))
                            dp[i][j]=min(dp[i][j],num+dp[i-(1<<j)][p]);
                    }
                }

            }
        }
        ans=MAX;
        for(int i=0;i<n;i++)
            ans=min(ans,dp[state][i]);
        printf("Scenario #%d:\n",++cas);
        printf("You have officially been pimped for only $%d\n\n",ans);

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HOJ 2252 The Priest(动态规划)

    The Priest Source : 计算机学院第二届“光熙杯”程序设计大赛 Time limit : 3 sec Memory limit...

    ShenduCC
  • HDU 2665 Kth number(可持续化线段树)

    Kth number Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768...

    ShenduCC
  • HDU 1074 Doing Homework(状压DP)

    Doing Homework Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

    ShenduCC
  • 【PAT甲级】Friend Numbers

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【POJ 3176】Cow Bowling(DP)

    The cows don't use actual bowling balls when they go bowling. They each take a n...

    饶文津
  • 【PAT甲级】1002 A+B for Polynomials (25分)

    This time, you are supposed to find A+B where A and B are two polynomials.

    韩旭051
  • 【2020HBU天梯赛训练】7-8 矩阵A乘以B

    给定两个矩阵A和B,要求你计算它们的乘积矩阵AB。需要注意的是,只有规模匹配的矩阵才可以相乘。即若A有R​a​​行、C​a​​列,B有R​b​​行、C​b​​列...

    韩旭051
  • 【HDU 4305】Lightning(生成树计数)

    There are N robots standing on the ground (Don't know why. Don't know how). 

    饶文津
  • hdu---(1054)Strategic Game(最小覆盖边)

    Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

    Gxjun
  • 找树根和孩子

    •【例3-1】找树根和孩子 【问题描述】   给定一棵树,输出树的根root,孩子最多的结点max以及他的孩子 【输入格式】   第一行:n(结点数<=100)...

    attack

扫码关注云+社区

领取腾讯云代金券