uva 374 Big Mod
赤裸裸的整數快速冪取模
#include <cstdio>
long long PowerMod(long long a, int b, int k)
{
long long tmp = a, ret = 1;
while (b)
{
if (b & 1)
ret = ret * tmp % k;
tmp = tmp * tmp % k;
b >>= 1;
}
return ret;
}
int main()
{
long long a;
int b, k;
while (scanf("%lld %d %d", &a, &b, &k) == 3)
printf("%lld\n", PowerMod(a, b, k));
return 0;
}
posted @
2009-03-15 10:58 sdfond 閱讀(1799) |
評論 (4) |
編輯 收藏
終于通了第三章。
這個題目我設的三維狀態，dp[i][j][k]表示前i個歌曲放在前j個唱片中第j個唱片用了k分鐘的最大歌曲數。
轉移方程：dp[i][j][k] = max{ dp[i-1][j][k-w[i]] + 1, dp[i-1][j][k], dp[i-1][j-1][p] } p = 0...t
跟背包問題差不多，就是加了一個唱片個數和容量的限制。三維狀態一維轉移，時間復雜度 O(n * m * t * t)
/*
ID: shyprom1
PROG: rockers
LANG: C++
*/
#include <cstdio>
int main()
{
freopen("rockers.in", "r", stdin);
freopen("rockers.out", "w", stdout);
const int N = 32;
int n, m, t, v, dp[N][N] = {0}, ans = 0;
scanf("%d %d %d", &n, &t, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &v);
for (int j = 1; j <= m; j++)
{
for (int k = t; k >= 0; k--)
{
for (int p = 1; p <= t; p++)
dp[j][k] >?= dp[j-1][p];
if (k >= v)
dp[j][k] >?= dp[j][k-v] + 1;
}
}
}
for (int i = 0; i <= t; i++)
ans >?= dp[m][i];
printf("%d\n", ans);
return 0;
}
posted @
2009-03-10 15:31 sdfond 閱讀(402) |
評論 (0) |
編輯 收藏
新學期開始了，新的挑戰繼續。
這個博客主要會寫一些算法的總結，并且貼一些代碼，供自己收藏吧，呵呵。
posted @
2009-03-09 11:58 sdfond 閱讀(191) |
評論 (0) |
編輯 收藏