题解 - Vijos

0

eurus LV 8 @ 2017-08-16 13:16:49

//记忆化搜索

#include<bits/stdc++.h>
using namespace std;

int t[100010];
int f[100010][4][4][4][4];
int n;

int getsum(int x, int y, int z){
if(x==0)
if(y==0||y==z) return 1;
else return 2;
int ret=3;
if(x==y||y==z||x==z) ret--;
if(x==y&&y==z) ret--;
return ret;
}

int solve(int i, int j, int k, int l, int m){
if(i==n+1) return 0;
if(f[i][j][k][l][m]!=-1) return f[i][j][k][l][m];
int ret=max(solve(i+1, k, t[i], l, m)+getsum(j, k, t[i]), solve(i+1, j, k, m, t[i])+getsum(l, m, t[i]));
return f[i][j][k][l][m]=ret;
}

int main(){
memset(f, -1, sizeof(f));
cin>>n;
string tmp;
cin>>tmp;
for(int i=0;i<n;i++){
char c=tmp[i];
if(c=='M') t[i+1]=1;
else if(c=='F') t[i+1]=2;
else t[i+1]=3;
}
int ans=solve(1, 0, 0, 0, 0);
cout<<ans<<endl;
return 0;
}

0

caesar_199 LV 9 @ 2016-08-11 20:19:17

测试数据 #0: Accepted, time = 0 ms, mem = 956 KiB, score = 8

测试数据 #1: Accepted, time = 15 ms, mem = 952 KiB, score = 8

测试数据 #2: Accepted, time = 0 ms, mem = 948 KiB, score = 8

测试数据 #3: Accepted, time = 0 ms, mem = 952 KiB, score = 8

测试数据 #4: Accepted, time = 0 ms, mem = 948 KiB, score = 8

测试数据 #5: Accepted, time = 0 ms, mem = 952 KiB, score = 8

测试数据 #6: Accepted, time = 0 ms, mem = 948 KiB, score = 8

测试数据 #7: Accepted, time = 0 ms, mem = 952 KiB, score = 8

测试数据 #8: Accepted, time = 0 ms, mem = 952 KiB, score = 8

测试数据 #9: Accepted, time = 0 ms, mem = 956 KiB, score = 8

测试数据 #10: Accepted, time = 31 ms, mem = 952 KiB, score = 10

测试数据 #11: Accepted, time = 46 ms, mem = 952 KiB, score = 10

Accepted, time = 92 ms, mem = 956 KiB, score = 100

技巧是用一个二位的三进制数表示该仓库前两天的配餐类型。
0表示M，1表示F，2表示B，两天一共有九种情况（00， 01， 02， 10， 11，12，20，21，22，用0到8来表示）。
一个特殊情况是该仓库还未配过餐，用9表示，另一个特殊情况是该仓库只配过一次餐，这种情况等价于前两天配餐种类相同。
而程序中的check函数返回的是如果三天的配餐种类分别为a，b，c，则矿工的出矿量为多少。
之后的动态规划就是很常规的思路了，边界条件是两个仓库都未配餐时总出矿量为0，值得注意的是刷表法要比一般的递推更好写，代码如下。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int INF = 1000000000;
const int maxn = 100000 + 10;
int n;
int d[10][10][2];

int readchar () {
    char c = getchar();
    if (c == 'M') return 0;
    if (c == 'F') return 1;
    if (c == 'B') return 2;
}

int check (int a, int b, int c) {
    if (a == b && b == c && a == c) return 1;
    if (a != b && a != c && b != c) return 3;
    return 2;
}

int main ()
{
//  freopen("in.txt", "r", stdin);
    cin >> n; getchar();
    
    for (int i = 0; i < 10; i++) 
        for (int j = 0; j < 10; j++) 
            d[i][j][0] = -INF;
    
    d[9][9][0] = 0;
    int t = 0;
    for (int cur = 0; cur < n; cur++) {
        for (int i = 0; i < 10; i++) 
            for (int j = 0; j < 10; j++) d[i][j][t^1] = -INF;
        
        int food = readchar();
        for (int i = 0; i < 10; i++) 
            for (int j = 0; j < 10; j++) if (d[i][j][t] >= 0) {
                if (i == 9) d[food*3+food][j][t^1] = max(d[food*3+food][j][t^1], d[i][j][t]+1);
                else {
                    int f1 = i/3, f2 = i%3;
                    int next = f2*3+food;
                    int v = check(f1, f2, food);
                    d[next][j][t^1] = max(d[next][j][t^1], d[i][j][t]+v);
                }
                
                if (j == 9) d[i][food*3+food][t^1] = max(d[i][food*3+food][t^1], d[i][j][t]+1);
                else {
                    int f1 = j/3, f2 = j%3;
                    int next = f2*3+food;
                    int v = check(f1, f2, food);
                    d[i][next][t^1] = max(d[i][next][t^1], d[i][j][t]+v);
                }
        }
        t ^= 1;
    }
    int ans = -INF;
    for (int i = 0; i < 10; i++) 
        for (int j = 0; j < 10; j++) ans = max(ans, d[i][j][t]);
    
    cout << ans;
    return 0;
}

0

ljt12138 LV 10 @ 2016-08-09 12:14:11

测试数据 #0: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #1: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #2: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #3: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #4: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #5: Accepted, time = 0 ms, mem = 1056 KiB, score = 8
测试数据 #6: Accepted, time = 0 ms, mem = 1052 KiB, score = 8
测试数据 #7: Accepted, time = 15 ms, mem = 1052 KiB, score = 8
测试数据 #8: Accepted, time = 46 ms, mem = 1056 KiB, score = 8
测试数据 #9: Accepted, time = 93 ms, mem = 1056 KiB, score = 8
测试数据 #10: Accepted, time = 203 ms, mem = 1056 KiB, score = 10
测试数据 #11: Accepted, time = 312 ms, mem = 1056 KiB, score = 10

Accepted, time = 669 ms, mem = 1056 KiB, score = 100
诡异的按层bfs+dp。边看法国虐中国，边调了一早上。。。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int n;
char str[100004];
int dp[2][5][5][5][5];
int has[5][5][5][5];
int food[100004];
struct pk {
int p, pp, t, tt;
pk()
{
p = pp = t = tt = 0;
}
};
queue<pk> que;
int delta(int i, int j, int k)
{
int ans = 0;
int did[4]; memset(did, 0, sizeof did);
if (i != 0 && !did[i]){did[i] = 1; ans++;}
if (j != 0 && !did[j]){did[j] = 1; ans++;}
if (k != 0 && !did[k]){did[k] = 1; ans++;}
return ans;
}

int main()
{
scanf("%d", &n);
scanf("%s", str+1);
memset(dp, -127, sizeof dp);
memset(has, 0, sizeof has);
for (int i = 1; i <= n; i++) {
switch(str[i]) {
case 'M': food[i] = 1; break;
case 'F': food[i] = 2; break;
case 'B': food[i] = 3; break;
}
}
pk a, b;
int now = 1, pre = 0;
que.push(a);
//has[0][0][0][0] = 1;
//cout << dp[1][1][1][1][1] << endl;
dp[pre][0][0][0][0] = 0;
for (int i = 1; i <= n; i++) {
int sz = que.size(), fd = food[i];
memset(has, 0, sizeof has);
for (int j = 1; j <= sz; j++) {
a = que.front(); que.pop();
if (has[a.p][a.pp][a.t][a.tt]) continue;
has[a.p][a.pp][a.t][a.tt] = 1;
b = a;
dp[now][fd][a.p][a.t][a.tt] = max(dp[now][fd][a.p][a.t][a.tt], dp[pre][a.p][a.pp][a.t][a.tt]+delta(a.p, a.pp, fd)); a.pp = a.p; a.p = fd;
dp[now][b.p][b.pp][fd][b.t] = max(dp[now][b.p][b.pp][fd][b.t], dp[pre][b.p][b.pp][b.t][b.tt]+delta(b.t, b.tt, fd)); b.tt = b.t; b.t = fd;
que.push(a);
que.push(b);
}
swap(now, pre);
}
int ans = 0;
while (!que.empty()) {
a = que.front(); que.pop();
ans = max(ans, dp[pre][a.p][a.pp][a.t][a.tt]);
}
cout << ans << endl;
return 0;
}

0

JSZX11556 LV 9 @ 2016-02-12 18:28:40

http://www.cnblogs.com/JSZX11556/p/4556177.html dp

0

nzhtl1477 LV 10 @ 2015-08-27 17:05:22

内存限制都不说真是可恶

0

yeziqing12 LV 8 @ 2012-10-02 16:08:44

├ 测试数据 01：答案正确... (133ms, 580KB)

├ 测试数据 02：答案正确... (0ms, 580KB)

├ 测试数据 03：答案正确... (0ms, 580KB)

├ 测试数据 04：答案正确... (0ms, 580KB)

├ 测试数据 05：答案正确... (0ms, 580KB)

├ 测试数据 06：答案正确... (0ms, 580KB)

├ 测试数据 07：答案正确... (0ms, 580KB)

├ 测试数据 08：答案正确... (0ms, 580KB)

├ 测试数据 09：答案正确... (0ms, 580KB)

├ 测试数据 10：答案正确... (0ms, 580KB)

├ 测试数据 11：答案正确... (0ms, 580KB)

├ 测试数据 12：答案正确... (0ms, 580KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 133ms / 580KB

第一个也是大数据吗。。。。。这不科学。。。。

0

xiaoX LV 10 @ 2010-03-27 17:35:58

├ 测试数据 11：答案正确... 103ms

├ 测试数据 12：答案正确... 244ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：347ms

新评测机速度还不错。。。

0

zhanghanyuan LV 10 @ 2010-03-14 21:15:45

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

├ 测试数据 11：答案正确... 244ms

├ 测试数据 12：答案正确... 525ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：810ms

评测机要CONNA哦

0

xman LV 8 @ 2009-11-07 09:41:04

晕，这道卡了我好久，换了好几个状态表示，最终还是投降了...看看题解的状态表示咋样，哎，为什么我就没想到呢...

后来数组开太大

var a1,a2,b1,b2,x:word;ch:char;n,i:longint;

f:array[0..100000,0..3,0..3,0..3,0..3]of longint;ans:longint;

s:array[0..100000]of word;

//d:array[0..3,0..3,1..3]of word;

后两点超了

最后采用了honghaijie神牛的方法，直接免去预处理，来优化内存，

var a1,a2,b1,b2,x:word;ch:char;n,i:longint;

f:array[0..100000,1..3,1..3,1..3,1..3]of longint;ans:longint;

s:array[0..100000]of word;

d:array[0..3,0..3,1..3]of word;

发个代码参考下：

var a1,a2,b1,b2,x:word;ch:char;n,i:longint;

f:array[0..100000,1..3,1..3,1..3,1..3]of longint;ans:longint;

s:array[0..100000]of word;

d:array[0..3,0..3,1..3]of word;

function max(a,b:longint):longint;

begin

max:=a;

if b>max then max:=b;

end;

function pd(a,b,c:integer):integer;

begin

if a=0 then a:=c;if b=0 then b:=c;

if ab then

begin

if a=c then exit(2)

else begin if b=c then exit(2) else exit(3); end;

end

else

if a=c then exit(1) else exit(2);

end;

begin

assign(input,'in.txt');

reset(input);

readln(n);

for i:=1 to n do

begin

read(ch);

if ch='M' then s[i]:=1

else if ch='F' then s[i]:=2

else if ch='B' then s[i]:=3;

end;

for a1:=0 to 3 do

for a2:=0 to 3 do

for b1:=1 to 3 do

d[a1,a2,b1]:=pd(a1,a2,b1); //预处理产煤量，优化时间

for i:=1 to n do

for a1:=1 to 3 do

for a2:=1 to 3 do

for b1:=1 to 3 do

for b2 :=1 to 3 do

f:=-10000; //为DP做准备

for i:=1 to n do

for a1:=1 to 3 do

for a2:=1 to 3 do

for b1:=1 to 3 do

for b2 :=1 to 3 do

for x:=1 to 3 do //DP

begin

f:=max(f,f+d[x,a1,s[i]]);

f:=max(f,f+d[x,b1,s[i]]);

end;

ans:=0;

for a1:=1 to 3 do

for a2:=1 to 3 do

for b1:=1 to 3 do

for b2:=1 to 3 do

if f[n,a1,a2,b1,b2]>ans then ans:=f[n,a1,a2,b1,b2]; //找出ans

writeln(ans-6);

end.

由于没有预处理，所以“程序会把第0次第-1次当做和第一次不一样的，实际上不是.. 所以-6"--摘至honghaijie神牛

0

453844077 LV 10 @ 2009-10-31 23:26:06

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 103ms

├ 测试数据 11：答案正确... 415ms

├ 测试数据 12：答案正确... 789ms

Vag 6K...

int cost(int a, int b, int c)

{

memset(exist, 0, sizeof(exist));

exist[a] = exist = exist[c] = true;

return count(exist, exist + 3, true);

}

滚动数组。。。

0

wuxiangyu LV 8 @ 2009-10-23 13:22:27

Accepted 有效得分：100 有效耗时：1169ms

有点慢...

四维数组即可...

要仔细写d(x,y,z)函数...

0

honghaijie LV 9 @ 2009-10-14 12:33:28

Accepted 有效得分：100 有效耗时：4515ms

够慢的！

然后又提交了vivid puppy

Accepted 有效得分：100 有效耗时：1419ms

咦还不错！

用的5维DP

最后结果减6就行了（如果n

0

chengrui LV 10 @ 2009-10-11 08:23:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 72ms

├ 测试数据 12：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：300ms

囧~~~~没秒杀，f,滚动数组

一次AC....

0

laz LV 10 @ 2009-09-27 09:56:38

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 431ms

├ 测试数据 11：答案正确... 1338ms

├ 测试数据 12：答案正确... 1994ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3882ms

一次AC~~

巨慢无比的程序O.O Orz我楼下O.O

ps:267

又提交了一次 Puppy测得 ^.^

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 150ms

├ 测试数据 11：答案正确... 603ms

├ 测试数据 12：答案正确... 931ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1684ms

0

xusc_2009 LV 9 @ 2009-09-23 21:05:50

├ 测试数据 11：答案正确... 1806ms

├ 测试数据 12：答案正确... 2697ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：5343ms

如果要比程序速度，我肯定是最慢的了……

程序50行

什么时候一定要去看一看压缩状态的方法，5维太暴力了些

关于算法：

主要的思路就是因为状态和最后两天有关，所以一定要记录一下

0

notblack LV 10 @ 2009-09-20 11:23:02

真乃好题也~

因为生产量的不同只跟两个矿的最后两次有关，所以开个5维的滚动数组就好了。

0

411789805 LV 8 @ 2009-08-30 12:50:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

├ 测试数据 11：答案正确... 275ms

├ 测试数据 12：答案正确... 509ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：856ms

忘了开ansistring 检查了一天

0

陈亮宇 LV 10 @ 2009-08-28 16:37:41

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

├ 测试数据 11：答案正确... 134ms

├ 测试数据 12：答案正确... 353ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：512ms

ps:228

0

hahacool LV 10 @ 2009-08-27 21:38:14

├ 测试数据 10：答案正确... 56ms

├ 测试数据 11：答案正确... 306ms

├ 测试数据 12：答案正确... 556ms

超级猥琐~

把一个计数函数变成常量数组就AC了

0

zjh77701 LV 8 @ 2009-08-18 22:03:25

很险地过了

puppy

program vijos1386;

var N,h,i,j,k,l,m,x,y,max:longint;

a:array[0..100000] of longint;

f,g:array[0..2,0..3,0..3,0..3,0..3] of longint;

ch:char;

function check(x,y,z:longint):longint;

var i,s:longint;

c:set of 1..3;

begin

c:=[x]+[y]+[z];

s:=0;

for i:=1 to 3 do

if i in c then s:=s+1;

check:=s;

end;

procedure clear;

var i,j,k,l,m:longint;

begin

for i:=1 to 2 do

for j:=0 to 3 do

for k:=0 to 3 do

for l:=0 to 3 do

for m:=0 to 3 do g:=-1;

g[1,0,0,0,0]:=0; g[2,0,0,0,0]:=0;

end;

begin

readln(N);

for i:=1 to N do begin

read(ch);

if ch='M' then a[i]:=1;

if ch='F' then a[i]:=2;

if ch='B' then a[i]:=3;

end;

for i:=1 to 2 do

for j:=0 to 3 do

for k:=0 to 3 do

for l:=0 to 3 do

for m:=0 to 3 do f:=-1;

f[1,0,0,0,0]:=0; f[2,0,0,0,0]:=0;

for h:=1 to N do begin

clear;

for i:=1 to 2 do

for j:=0 to 3 do

for k:=0 to 3 do

for l:=0 to 3 do

for m:=0 to 3 do

if f-1 then begin

x:=f+check(j,k,a[h]);

if x>g[1,k,a[h],l,m] then g[1,k,a[h],l,m]:=x;

y:=f+check(l,m,a[h]);

if y>g[2,j,k,m,a[h]] then g[2,j,k,m,a[h]]:=y;

end;

f:=g;

end;

max:=0;

for i:=1 to 2 do

for j:=1 to 3 do

for k:=1 to 3 do

for l:=1 to 3 do

for m:=1 to 3 do

if f>max then max:=f;

writeln(max);

end.

PS：第223人

题解

42 条题解

矿工配餐

信息

状态

开发

支持

题解

42 条题解

矿工配餐

信息

状态

开发

支持

还没有账户？

登录