首页 > ACM题库 > HDU-杭电 > HDU 4152-ZZY’s Dilemma[解题报告]HOJ
2015
04-16

HDU 4152-ZZY’s Dilemma[解题报告]HOJ

ZZY’s Dilemma

问题描述 :

ZZY has many habits like seeing movie, listening music, playing PC game and football and so on. Besides he has many goals, as not every habit is good for achieving his goals, he falls into the dilemma of making a choice between his goals and habits.
Now ,we define the effect that one habit has on each goal is represented as a vector,and the elements of the vector are integers,ex.vector(100,90,-10,80)means it has 100 point effect on goal 1,90 point effect on goal 2,-10 point effect on goal 3 and 80 point effect on goal 4(the positive point means good effect and the negative point means bad effect),and the given requirement of each goal is represented as integer.please help ZZY to achieve his goals as well as keeps his habits as many as possible.

输入:

There are multi cases , read the data until EOF.( No more than 10 cases )
Line 1: The number of ZZY’s goals N(0<N<=20)
Line 2: The requirement of each goals (0 < w <= 1000)
Line 3: The number of ZZY’s habits M(0 < M <= 16)
Line 4-M+4: Each line contains N integers, the ith integer represents the effect on ith goal (-1000 <= data <= 1000).

输出:

There are multi cases , read the data until EOF.( No more than 10 cases )
Line 1: The number of ZZY’s goals N(0<N<=20)
Line 2: The requirement of each goals (0 < w <= 1000)
Line 3: The number of ZZY’s habits M(0 < M <= 16)
Line 4-M+4: Each line contains N integers, the ith integer represents the effect on ith goal (-1000 <= data <= 1000).

样例输入:

4
100 200 300 400
3
100 100 400 500
100 -10 50  300
100 100 -50  -50

样例输出:

2 1 3

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int g[22], ans[22], h[22][22];
int n, m, goal, habit, num;
bool vis[22];

void dfs(int s, int t)
{
    if(t == num)
    {
        int sum, k = 1;
        for(int i = 0; i < n; i++)
        {
            sum = 0;
            for(int j = 0; j < m; j++)
                if(vis[j])
                    sum += h[j][i];
            if(sum < g[i])
                k = 0;
        }
        if(k && t > habit)
        {
            habit = t;
            for(int i = 0, x = 0; i < m; i++)
                if(vis[i])
                    ans[x++] = i;
        }
        return ;
    }
    for(int i = s; i < m; i++)
    {
        if(!vis[i])
        {
            vis[i] = 1;
            dfs(i + 1, t + 1);
            vis[i] = 0;
        }
    }
    return ;
}

int main()
{
    int i, j;
    while(scanf("%d", &n) != EOF)
    {
        for(i = 0; i < n; i++)
            scanf("%d", &g[i]);
        scanf("%d", &m);
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &h[i][j]);
        habit = goal = 0;
        for(i = m; i > 0; i--)
        {
            memset(vis, 0, sizeof(vis));
            num = i;
            dfs(0, 0);
        }
        printf("%d", habit);
        for(i = 0; i < habit; i++)
            printf(" %d", ans[i] + 1);
        printf("\n");
    }
}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }