uva1508-Equipment 状态压缩 记忆化搜索

admin管理员组

文章数量:1530518

The Korea Defense and Science Institute, shortly KDSI, has been putting constant effort into new equipment for individual soldiers for recent years , and at last released N new types of equipment. KDSI has already done evaluation of each of the N types of equipment , finally resulting in scores in five categories: attack improvement, defense improvement, vision improvement, portability, and easiness of usage. The score in each category is quantified as an integer in the range 0 to 10 , 0 00 , and the rating of each type of equipment is thus represented as a sequence of five integers. In consideration of costs and capability of average individual soldier s, KDSI also reported that each soldier will be able to install at most K types of equipment on his body to extend his ability. If a single type is installed on a soldier, then his ability in each category is extended by the specified score of that type. M oreover, if a soldier installs more than one type of equipment, then his ability in each category is extended by the maximum score of the chosen types in that category. For example, if the vision improvement scores of type a and type b are 10 and 15, respe ctively, then installing a combination of two types a and b will result in a vision improvement by their maximum score 15. We call the maximum score 15 the extension score of a category ; so, the extension score of vision improvement for combination { a , b } is 15 in this example. KDSI now started devising a way of finding an optimal combination of K type s of equipment for best performance of individual soldiers. While a force can sometimes be of a special purpose so that a certain category would be more important than the others, every single category is, however, regarded equally important in general. Fo r this general purpose, KDSI defined the objective score of a combination of equipment to be the sum of the extension scores of the five categories for the combination. KDSI thus wants to find a best combination of K types of equipment such that its object ive score is maximized among all possible combinations of K types. You are asked by KDSI to devise and write a computer program that finds the objective score of a best combination of K types of equipment, that is, the maximum possible objective score for all possible combinations of K types among the given N types of equipment. Put differently , you are given N types of equipment {1, , N } and their ratings R i represented by five integers R i = ( r i , 1 , r i , 2 , r i , 3 , r i ,4 , r i ,5 ) with 0 r i , j 10,000 for each i , N and j = 1, , 5. Given a nother natural number K (1 K N ) , your program has to compute the objective score of a best combination of K types of equipment. For example, consider an input instance in which N = 4, K = 2, and each R i is given as below: R 1 = (30, 30, 30, 30, 0) R 2 = (5 0, 0, 0, 0, 0) R 3 = (0, 50, 0, 50, 10) R 4 = (0, 0, 50, 0, 20). Then, choosing R 1 and R 3 forms a best combination of two types {1, 3} and yields the objective score 30+50+30+50+10 = 170, which will be the answer of a correct program

  从N组装备中选K组，求这K组1-5每个位置最大的数的和。
  这个题思路很神奇。。因为是分成几组，可以想某个组某几个数的和最大，另外的组另一些数的和最大。所以可以以某几个数作为一组为基础遍历，找这么K组构成全部的5个数，并且选的某几个数一定是N个人里这几个数的和最大的那个。每组只有5个数，状态最大才31（11111），用f[i]表示N组里状态i时的最大值（二进制为1的位置的数的和）。DP的时候遍历所有状态，答案是DP(31,0) （一开始11111，这5个数都没有被确定，已选了0组）。
  比如现在要递归11111，选中状态10100，就是选1，3和最大的那一组，接着递归01011。
  为什么这样是对的呢？是因为如果选K组得到的答案比选K-1组答案大的话，最后选中的每组里面一定有一个状态是N组里这个状态的最大值（如果不是最大值就可以找更大的不在已选中的代替得到更优答案）。如果选K组和选K-1组答案一样，就有两次选的状态最大值都是同一组的情况，这样也没有影响，多出的组数可以随便选。

  做了这个题我才发现，原来找某个状态没有任何一位大于它的其他状态是用这个方法。。for(int i=st;i;i=(i-1)&st)。。我以前做过一个这样的，还是i一个一个减，然后判断每位。。这个方法一下就避免了减的过程中0变成1的情况，相当于跳着减，（如果变成1，一下就减掉了前面不变，那一位是1，后面不管任何数的情况）。
  还有i^st，是st除掉i状态的表示的好方法。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define INF 0x3f3f3f3f
#define MAXN 10010
#define MAXM 60
#define eps 1e-9
#define pii pair<int,int>
using namespace std;
int T,N,K,f[40],d[40][6],a[MAXN][6];
int DP(int st,int dep){
    int &ans=d[st][dep];
    if(ans!=-1) return ans;
    ans=0;
    if(dep==K) return 0;
    for(int i=st;i;i=(i-1)&st) ans=max(ans,f[i]+DP(st^i,dep+1));
    return ans;
}
int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&K);
        memset(f,0,sizeof(f));
        memset(d,-1,sizeof(d));
        int sum=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<5;j++){
                scanf("%d",&a[i][j]);
                sum+=a[i][j];
            }
            for(int st=0;st<32;st++){
                int s=0;
                for(int j=0;j<5;j++) if(st&(1<<j)) s+=a[i][j];
                f[st]=max(f[st],s);
            }
        }
        if(K>=N) printf("%d\n",sum);
        else printf("%d\n",DP(31,0));
    }
    return 0;
}

本文标签： 状态记忆equipment