BestCoder Round #63(Div.2) (4/4) (Div.1) (3/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

21 11月 2015

A sequence1

Problem Description

Given an array a with length n, could you tell me how many pairs (i,j) ( i < j ) for abs(ai−aj) mod b=c.

Input

Several test cases(about 5)

For each cases, first come 3 integers, n,b,c(1≤n≤100,0≤c<b≤109)

Then follows n integers ai(0≤ai≤109)

Output

For each cases, please output an integer in a line as the answer.

Sample Input

3 3 2
1 2 3
3 3 1
1 2 3

Sample Output

Source

BestCoder Round #63 (div.2)

题目类型：枚举

算法分析：直接双重枚举+判断即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define    DB(ccc)    cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e4 + 66;

int aa[maxn];

int main()
{
//    CFF;
    int n, b, c;
    while (scanf ("%d", &n) != EOF)
    {
        scanf ("%d %d", &b, &c);
        int res = 0;
        for (int i = 1; i <= n; i++)
            scanf ("%d", &aa[i]);

        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
                if (abs (aa[i] - aa[j]) % b == c)
                    res++;
        }

        printf ("%d\n", res);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e4 + 66;

int aa[maxn];

int main()

{

// CFF;

int n, b, c;

while (scanf ("%d", &n) != EOF)

{

scanf ("%d %d", &b, &c);

int res = 0;

for (int i = 1; i <= n; i++)

scanf ("%d", &aa[i]);

for (int i = 1; i <= n; i++)

{

for (int j = i + 1; j <= n; j++)

if (abs (aa[i] - aa[j]) % b == c)

res++;

}

printf ("%d\n", res);

}

return 0;

}

B sequence2

Problem Description

Given an integer array bi with a length of n, please tell me how many exactly different increasing subsequences. P.S. A subsequence bai(1≤i≤k) is an increasing subsequence of sequence bi(1≤i≤n) if and only if 1≤a1<a2<...<ak≤n and ba1<ba2<...<bak.
Two sequences ai and bi is exactly different if and only if there exist at least one i and ai≠bi.

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,k(1≤n≤100,1≤k≤n)

Then follows n integers ai(0≤ai≤109)

Output

For each cases, please output an integer in a line as the answer.

Sample Input

3 1
1 2 2
3 2
1 2 3

Sample Output

Source

BestCoder Round #63 (div.2)

题目类型：二维dp

算法分析：dp[i][j]表示长度为i且最后一个数字为j所构成的不同子序列个数，状态转移方程为dp[i][j] = Sigma dp[i-1][k](1 <= k <= j - 1且ak < aj)。注意看清题目！！！注意要使用高精度求解！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000;

const int MAXSIZE = 1e3;
struct BigInt
{
    int len, s[MAXSIZE];
    BigInt () {memset(s, 0, sizeof(s)); len = 1;}
    BigInt (int num) {*this = num;}
    BigInt (const char *num) {*this = num;}

    BigInt operator = (const int num)
    {
        char s[MAXSIZE];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    BigInt operator = (const char *num)
    {
        for (int i = 0; num[i] == '0'; num++) ;
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }

    void CleanFrontZero () {while (len > 1 && !s[len-1]) len--;}

    BigInt operator + (const BigInt &b) const
    {
        BigInt c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }

    BigInt operator - (const BigInt &b)//要满足被减数比减数大
    {
        BigInt c;
        c.len = 0;
        for (int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0) g = 0;

            else {g = 1; x += 10;}
            c.s[c.len++] = x;
        }
        c.CleanFrontZero();
        return c;
    }

    BigInt operator * (const BigInt &b)
    {
        BigInt c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < b.len; j++)
                c.s[i + j] += s[i] * b.s[j];

        for (int i = 0; i < c.len; i++)
        {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.CleanFrontZero();
        return c;
    }

    BigInt operator / (const BigInt &b)//整数除法，即只保留结果的整数部分
    {
        BigInt c, f = 0;
        for (int i = len - 1; i >= 0; i--)
        {
            f = f * 10;
            f.s[0] = s[i];
            while (f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.CleanFrontZero();
        return c;
    }

    bool operator < (const BigInt &b)
    {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }

    bool operator > (const BigInt &b)
    {
        if (len != b.len) return len > b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] > b.s[i];
        return false;
    }

    BigInt operator % (const BigInt &b) { BigInt r = *this / b; r = *this - r * b; return r;}
    BigInt operator += (const BigInt &b) {*this = *this + b; return *this;}
    BigInt operator -= (const BigInt &b) {*this = *this - b; return *this;}
    BigInt operator *= (const BigInt &b) {*this = *this * b; return *this;}
    BigInt operator /= (const BigInt &b) {*this = *this / b; return *this;}
    BigInt operator %= (const BigInt &b) {*this = *this % b; return *this;}
    bool operator == (const BigInt &b) {return !(*this > b) && !(*this < b);}
    bool operator != (const BigInt &b) {return !(*this == b);}
    bool operator <= (const BigInt &b) {return *this < b || *this == b;}
    bool operator >= (const BigInt &b) {return *this > b || *this == b;}
    BigInt Inc (int v = 1) {*this += v; return *this;}
    BigInt Dec (int v = 1) {*this -= v; return *this;}

    string str() const
    {
        string res = "";
        for (int i = 0; i < len; i++) res = char(s[i] + '0') + res;
        return res;
    }
};

istream& operator >> (istream &in, BigInt &x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const BigInt &x)
{
    if (x.len > 0) out << x.str();//非常重要的地方！！！
    else out << "0";
    return out;
}

//高精度阶乘
BigInt Factorial (int n)
{
    BigInt base = 1;
    for (int i = 2; i <= n; i++) base *= i;
    return base;
}

//高精度阶乘
BigInt Factorial (BigInt n)
{
    BigInt res = 1;
    for (BigInt base = 2; base <= n; base.Inc()) res *= base;
    return res;
}

//高精度幂
BigInt Pow (BigInt a, int b)
{
    BigInt s = 1;
    while (b)
    {
        if (b & 1) s *= a;
        a *= a;
        b >>= 1;
    }
    return s;
}

BigInt dp[126][126];
int aa[126];

int main()
{
//    CFF;
    int n, k;
    while (scanf ("%d %d", &n, &k) != EOF)
    {
        for (int i = 0; i < 126; i++)
            for (int j = 0; j < 126; j++)
                dp[i][j] = 0;

        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &aa[i]);
            dp[1][i] = 1;
        }

        for (int i = 2; i <= k; i++)
        {
            for (int j = i; j <= n; j++)
            {
                for (int q = 1; q <= j - 1; q++)
                {
                    if (aa[j] > aa[q] && q >= i - 1)
                        dp[i][j] = dp[i][j] + dp[i-1][q];
                }
            }
        }

        BigInt res = 0, tt = 0;
        for (int i = 1; i <= n; i++)
            res = res + dp[k][i];

        cout << res << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000;

const int MAXSIZE = 1e3;

struct BigInt

{

int len, s[MAXSIZE];

BigInt () {memset(s, 0, sizeof(s)); len = 1;}

BigInt (int num) {*this = num;}

BigInt (const char *num) {*this = num;}

BigInt operator = (const int num)

{

char s[MAXSIZE];

sprintf(s, "%d", num);

*this = s;

return *this;

}

BigInt operator = (const char *num)

{

for (int i = 0; num[i] == '0'; num++) ;

len = strlen(num);

for (int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';

return *this;

}

void CleanFrontZero () {while (len > 1 && !s[len-1]) len--;}

BigInt operator + (const BigInt &b) const

{

BigInt c;

c.len = 0;

for (int i = 0, g = 0; g || i < max(len, b.len); i++)

{

int x = g;

if (i < len) x += s[i];

if (i < b.len) x += b.s[i];

c.s[c.len++] = x % 10;

g = x / 10;

}

return c;

}

BigInt operator - (const BigInt &b)//要满足被减数比减数大

{

BigInt c;

c.len = 0;

for (int i = 0, g = 0; i < len; i++)

{

int x = s[i] - g;

if (i < b.len) x -= b.s[i];

if (x >= 0) g = 0;

else {g = 1; x += 10;}

c.s[c.len++] = x;

}

c.CleanFrontZero();

return c;

}

BigInt operator * (const BigInt &b)

{

BigInt c;

c.len = len + b.len;

for (int i = 0; i < len; i++)

for (int j = 0; j < b.len; j++)

c.s[i + j] += s[i] * b.s[j];

for (int i = 0; i < c.len; i++)

{

c.s[i + 1] += c.s[i] / 10;

c.s[i] %= 10;

}

c.CleanFrontZero();

return c;

}

BigInt operator / (const BigInt &b)//整数除法，即只保留结果的整数部分

{

BigInt c, f = 0;

for (int i = len - 1; i >= 0; i--)

{

f = f * 10;

f.s[0] = s[i];

while (f >= b)

{

f -= b;

c.s[i]++;

}

c.len = len;

c.CleanFrontZero();

return c;

}

bool operator < (const BigInt &b)

{

if (len != b.len) return len < b.len;

for (int i = len - 1; i >= 0; i--)

if (s[i] != b.s[i]) return s[i] < b.s[i];

return false;

}

bool operator > (const BigInt &b)

{

if (len != b.len) return len > b.len;

for (int i = len - 1; i >= 0; i--)

if (s[i] != b.s[i]) return s[i] > b.s[i];

return false;

}

BigInt operator % (const BigInt &b) { BigInt r = *this / b; r = *this - r * b; return r;}

BigInt operator += (const BigInt &b) {*this = *this + b; return *this;}

BigInt operator -= (const BigInt &b) {*this = *this - b; return *this;}

BigInt operator *= (const BigInt &b) {*this = *this * b; return *this;}

BigInt operator /= (const BigInt &b) {*this = *this / b; return *this;}

BigInt operator %= (const BigInt &b) {*this = *this % b; return *this;}

bool operator == (const BigInt &b) {return !(*this > b) && !(*this < b);}

bool operator != (const BigInt &b) {return !(*this == b);}

bool operator <= (const BigInt &b) {return *this < b || *this == b;}

bool operator >= (const BigInt &b) {return *this > b || *this == b;}

BigInt Inc (int v = 1) {*this += v; return *this;}

BigInt Dec (int v = 1) {*this -= v; return *this;}

string str() const

{

string res = "";

for (int i = 0; i < len; i++) res = char(s[i] + '0') + res;

return res;

}

};

istream& operator >> (istream &in, BigInt &x)

{

string s;

in >> s;

x = s.c_str();

return in;

}

ostream& operator << (ostream &out, const BigInt &x)

{

if (x.len > 0) out << x.str();//非常重要的地方！！！

else out << "0";

return out;

}

//高精度阶乘

BigInt Factorial (int n)

{

BigInt base = 1;

for (int i = 2; i <= n; i++) base *= i;

return base;

}

//高精度阶乘

BigInt Factorial (BigInt n)

{

BigInt res = 1;

for (BigInt base = 2; base <= n; base.Inc()) res *= base;

return res;

}

//高精度幂

BigInt Pow (BigInt a, int b)

{

BigInt s = 1;

while (b)

{

if (b & 1) s *= a;

a *= a;

b >>= 1;

}

return s;

}

BigInt dp[126][126];

int aa[126];

int main()

{

// CFF;

int n, k;

while (scanf ("%d %d", &n, &k) != EOF)

{

for (int i = 0; i < 126; i++)

for (int j = 0; j < 126; j++)

dp[i][j] = 0;

for (int i = 1; i <= n; i++)

{

scanf ("%d", &aa[i]);

dp[1][i] = 1;

}

for (int i = 2; i <= k; i++)

{

for (int j = i; j <= n; j++)

{

for (int q = 1; q <= j - 1; q++)

{

if (aa[j] > aa[q] && q >= i - 1)

dp[i][j] = dp[i][j] + dp[i-1][q];

}

BigInt res = 0, tt = 0;

for (int i = 1; i <= n; i++)

res = res + dp[k][i];

cout << res << endl;

}

return 0;

}

C matrix

Problem Description

Given a matrix with n rows and m columns ( n+m is an odd number ), at first , you begin with the number at top-left corner (1,1) and you want to go to the number at bottom-right corner (n,m). And you must go right or go down every steps. Let the numbers you go through become an array a1,a2,...,a2k. The cost is a1∗a2+a3∗a4+...+a2k−1∗a2k. What is the minimum of the cost?

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,m(1≤n≤1000,1≤m≤1000)

N+m is an odd number.

Then follows n lines with m numbers ai,j(1≤ai≤100)

Output

For each cases, please output an integer in a line as the answer.

Sample Input

2 3
1 2 3
2 2 1
2 3
2 2 1
1 2 4

Sample Output

Source

BestCoder Round #63 (div.2)

题目类型：二维线性dp

算法分析：dp[i][j]表示到(i, j)位置所具有的最小花费。若i + j为偶数，则dp[i][j] = min(dp[i-1][j], dp[i][j-1])。若i + j为奇数，则dp[i][j] = min(dp[i-1][j] + aa[i-1][j] * aa[i][j], dp[i][j-1] + aa[i][j-1] * aa[i][j])

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 66;

int dp[maxn][maxn], aa[maxn][maxn];

int main()
{
//    CFF;
    int row, col;
    while (scanf ("%d %d", &row, &col) != EOF)
    {
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                scanf ("%d", &aa[i][j]);

        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
            {
                if (i == 1 && j == 1) dp[i][j] = 0;

                else if (i == 1)
                {
                    if ((i + j) % 2 == 0) dp[i][j] = dp[i][j-1];
                    else dp[i][j] = dp[i][j-1] + aa[i][j-1] * aa[i][j];
                }

                else if (j == 1)
                {
                    if ((i + j) % 2 == 0) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = dp[i-1][j] + aa[i-1][j] * aa[i][j];
                }

                else
                {
                    if ((i + j) % 2 == 0) dp[i][j] = min (dp[i-1][j], dp[i][j-1]);
                    else dp[i][j] = min (dp[i-1][j] + aa[i-1][j] * aa[i][j], dp[i][j-1] + aa[i][j-1] * aa[i][j]);
                }
            }
        }
        printf ("%d\n", dp[row][col]);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 66;

int dp[maxn][maxn], aa[maxn][maxn];

int main()

{

// CFF;

int row, col;

while (scanf ("%d %d", &row, &col) != EOF)

{

for (int i = 1; i <= row; i++)

for (int j = 1; j <= col; j++)

scanf ("%d", &aa[i][j]);

for (int i = 1; i <= row; i++)

{

for (int j = 1; j <= col; j++)

{

if (i == 1 && j == 1) dp[i][j] = 0;

else if (i == 1)

{

if ((i + j) % 2 == 0) dp[i][j] = dp[i][j-1];

else dp[i][j] = dp[i][j-1] + aa[i][j-1] * aa[i][j];

}

else if (j == 1)

{

if ((i + j) % 2 == 0) dp[i][j] = dp[i-1][j];

else dp[i][j] = dp[i-1][j] + aa[i-1][j] * aa[i][j];

}

else

{

if ((i + j) % 2 == 0) dp[i][j] = min (dp[i-1][j], dp[i][j-1]);

else dp[i][j] = min (dp[i-1][j] + aa[i-1][j] * aa[i][j], dp[i][j-1] + aa[i][j-1] * aa[i][j]);

}

printf ("%d\n", dp[row][col]);

}

return 0;

}

D balls

Problem Description

There are n balls with m colors. The possibility of that the color of the i-th ball is color j is ai,jai,1+ai,2+...+ai,m. If the number of balls with the j-th is x, then you should pay x2 as the cost. Please calculate the expectation of the cost.

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,m(1≤n≤1000,1≤m≤1000)

Then follows n lines with m numbers ai,j(1≤ai≤100)

Output

For each cases, please output the answer with two decimal places.

Sample Input

2 2
1 1
3 5

2 2
4 5
4 2

2 2
2 4
1 4

Sample Output

3.00

2.96

3.20

Source

BestCoder Round #63 (div.2)

题目类型：概率期望

算法分析：大致的思路是根据概率期望的线性可加性，将每种情况分开考虑。一个非常重要的一点是：将具有第i种颜色小球个数v和具有第i种颜色的小球(可重复)的对数之间建立了一一对应的关系，详细解法可以参考：

http://blog.csdn.net/snowy_smile/article/details/50032485#comments

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 66;

double dp[maxn][maxn];

int main()
{
//    CFF;
    int row, col;
    while (scanf ("%d %d", &row, &col) != EOF)
    {
        for (int i = 1; i <= row; i++)
        {
            double tt = 0;
            for (int j = 1; j <= col; j++)
            {
                scanf ("%lf", &dp[i][j]);
                tt += dp[i][j];
            }
            for (int j = 1; j <= col; j++)
                dp[i][j] /= tt;
        }

        double res = 0;
        for (int i = 1; i <= col; i++)
        {
            double tt = 0;
            for (int j = 1; j <= row; j++)
            {
                res += dp[j][i] - dp[j][i] * dp[j][i];
                tt += dp[j][i];
            }

            res += tt * tt;
        }

        printf ("%.2lf\n", res);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 66;

double dp[maxn][maxn];

int main()

{

// CFF;

int row, col;

while (scanf ("%d %d", &row, &col) != EOF)

{

for (int i = 1; i <= row; i++)

{

double tt = 0;

for (int j = 1; j <= col; j++)

{

scanf ("%lf", &dp[i][j]);

tt += dp[i][j];

}

for (int j = 1; j <= col; j++)

dp[i][j] /= tt;

}

double res = 0;

for (int i = 1; i <= col; i++)

{

double tt = 0;

for (int j = 1; j <= row; j++)

{

res += dp[j][i] - dp[j][i] * dp[j][i];

tt += dp[j][i];

}

res += tt * tt;

}

printf ("%.2lf\n", res);

}

return 0;

}

hdu1260

hdu2159

超客的水墨烟雨

BestCoder Round #63(Div.2) (4/4) (Div.1) (3/4)

A sequence1

B sequence2

C matrix

D balls

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31