UVALive - 4905 Pro-Test Voting

题意：某人竞选，花钱 拉票，每个社区都有相应的信息，按照公式求出得票数（四舍五入）结果一样的时候（按 第一个社区的花费最多为准，依次类推）

思路：竟然要求结果一样的时候，按靠前的社区的花费多的为准，那么显然我们要从前往前推，按照背包的思想递推，dp[i][j]表示从第i个社区到n-1个社区花费j-k的最大得票数

还有的地方就是要标记在第i个的花费

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 110;

struct node{
    int N,Ip,R;
}arr[MAXN];
int dp[MAXN][MAXN],f[MAXN][MAXN];
int n,m;

int main(){
    int t = 1;
    while (scanf("%d%d",&m,&n) && n+m){
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        printf("Case %d: ",t++);
        for (int i = 0; i < n; i++)
            scanf("%d%d%d",&arr[i].N,&arr[i].Ip,&arr[i].R);
        for (int i = 0; i <= 100; i++){
            dp[n-1][i] = (arr[n-1].Ip+i/(i+10.1)*arr[n-1].R)/100*arr[n-1].N+0.5;
            f[n-1][i] = i;
        }
        for (int i = n-2; i >= 0; i--)
            for (int j = 0; j <= 100; j++){
                int Max = 0,Maxk;
                for (int k = 0; k <= j; k++){
                    int temp = (int)(dp[i+1][j-k]+(arr[i].Ip+k/(k+10.1)*arr[i].R)/100*arr[i].N+0.5);
                    if (temp >= Max){
                        Max = temp;
                        Maxk = k;
                    }
                    dp[i][j] = Max;
                    f[i][j] = Maxk;
                }
            }
        printf("%d\n",dp[0][m]);
        int temp = m,flag = 1;
        for (int i = 0; i < n; i++){
            if (flag){
                printf("%d:%d",i,f[i][temp]);
                flag = 0;
            }
            else printf(" %d:%d",i,f[i][temp]);
            temp -= f[i][temp];
        }
        printf("\n");
    }
    return 0;
}

UVALive - 4905 Pro-Test Voting

原文：http://blog.csdn.net/u011345136/article/details/18674543