学车思考之一:方向盘转多少,车轮就转多少度对吗?

时间：2014-04-07 02:18:43 阅读：1336 评论：0 收藏：0 [点我收藏+]

转载请注明出处

比赛链接

A：

略

B：

最多只有3个数，放心大胆的去暴力就可以了

关于原因暂时不明

C：

各种背包

按照题目给出的顺序从0~12对装备种类标号

对于种类0~8，做每组最多选一样的分组背包

对于种类9，做选0,1,2个的背包

然后再开一个数组，为kind 10和11两种物品的每组最多选一样背包，和只选kind 12双手武器的情况合并，

然后最后再把各种背包合并，得解

卧槽讲得好复杂，还是贴代码好了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define rep(i,x) for (int i = 0; i < (int)(x); i ++)

const int N = 50500;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
map<string,int> mp;
string Kind[13] = {"Head", "Shoulder", "Neck", "Torso", "Hand", "Wrist", "Waist", "Legs", 
        "Feet", "Finger", 
        "Shield", "Weapon", "Two-Handed"};
int n,m,dp[2][N],oh[N],*cur,*nex,fp[3][N],ed[N];
vector<PII> wp[13];


void init() {
        for (int i = 0; i < 13; i ++) {
                mp[Kind[i]] = i;
        }
}
inline void clear(int *X,int len = m) {
        for (int i = 0; i < len+10; i ++) X[i] = -INF;
}
inline void toMax(int &a,int b) { if (a<b) a = b; }
int work() {
        cur = dp[0];
        nex = dp[1];
        clear(cur);
        clear(nex);
        cur[0] = 0;
        int D,T;
        for (int i = 0; i < 9; i ++) {
                for (int j = 0; j <= m; j ++) nex[j] = cur[j];
                rep(j,wp[i].size()) {
                        D = wp[i][j].first;
                        T = wp[i][j].second;
                        for (int k = m; k >= 0; k --) if (cur[k]>=0) {
                                toMax(nex[min(m,k+T)],cur[k]+D);
                        }
                }
                swap(cur,nex);
        }
        for (int i = 0; i < 3; i ++) clear(fp[i]);
        for (int i = 0; i <= m; i ++) fp[0][i] = cur[i];
        rep(i,wp[9].size()) {
                D = wp[9][i].first;
                T = wp[9][i].second;
                for (int j = m; j >= 0; j --) {
                        for (int k = 1; k >= 0; k --) if (fp[k][j]>=0) {
                                toMax(fp[k+1][min(j+T,m)],fp[k][j]+D);
                        }
                }
        }
        clear(ed);
        for (int i = 0; i < 3; i ++) {
                for (int j = 0; j <= m; j ++) {
                        toMax(ed[j],fp[i][j]);
                }
        }
        clear(cur);
        clear(nex);
        cur[0] = 0;
        for (int i = 10; i <= 11; i ++) {
                for (int j = 0; j <= m; j ++) nex[j] = cur[j];
                rep(j,wp[i].size()) {
                        int T = wp[i][j].first;
                        int D = wp[i][j].second;
                        for (int k = 0; k <= m; k ++) if (cur[k]>=0) {
                                toMax(nex[min(k+D,m)],cur[k]+T);
                        }
                }
                swap(cur,nex);
        }
        rep(i,wp[12].size()) {
                int T = wp[12][i].first;
                int D = wp[12][i].second;
                toMax(cur[D],T);
        }
        cur[0] = -INF;
        for (int i = m-1; i >= 0; i --) {
                toMax(cur[i],cur[i+1]);
        }
        int ret = ed[m];
        for (int i = 0; i <= m; i ++) {
                if (ed[i]>=0 && cur[m-i]>=0) {
                        toMax(ret,ed[i]+cur[m-i]);
                }
        }
        if (ret<0) return -1;
        return ret;
}

int main() {
        int cas;
        ios::sync_with_stdio(false);
        init();
        cin >> cas;
        while (cas--) {
                cin >> n >> m;
                for (int i = 0; i < 13; i ++) {
                        wp[i].clear();
                }
                for (int i = 0; i < n; i ++) {
                        string s; int a,b;
                        cin >> s >> a >> b;
                        wp[mp[s]].push_back(PII(a,b));
                }
                cout << work() << endl;
        }
        return 0;
}

D：

此题无坑，按照他给出的优先级，排个序，然后分配一下LV就好了

F：

比赛时我们的解法是对每个节点开一个2*2矩阵(具体可以类比矩阵求斐波那契第n项)，然后线段树维护区间矩阵积，

实际上线段树可以通过维护前缀逆矩阵来略去，

再炫酷一点可以解方程...