pku1294 极角序应用

Leave a Comment2008.08.25 11:14　by Felicia　

这个题跟 pku1259 The Picnic 有些类似。具体做法是将除原点外所有点在全平面内极角排序，然后DP：
枚举起点`i`，设`f[j][k]`表示用`k`根橡皮筋圈住`i..j`的最小面积，可以转移到`f[j'][k + 1]`。
这样DP的时间复杂度是`O(bn^3)`。我一开始写的版本超时了，后来优化常数过的，很慢。如果有更好的做法请告诉我@_@

下面是我的主要代码
[Read more]

[动态规划] pku1080 二维DP

Leave a Comment2007.10.12 22:25　by Felicia　

很简单的DP，也是很基础的DP。做法就不说啦：）

下面是我的代码

下载: pku1080.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int n,i,j,k,la,lb;
char a[101],b[101];
int aa[101],bb[101];
int f[101][101];
int d[5][5]={5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,-2,-2,-1,-2,-2,5,-1,-3,-4,-2,-1,0};
 
main(){
    scanf("%d",&n);
    for (k=1;k<=n;k++){
        scanf("%d%s",&la,a);
        scanf("%d%s",&lb,b);
        for (i=0;i<=la-1;i++)
            if (a[i]=='A') aa[i+1]=0;
            else if (a[i]=='C') aa[i+1]=1;
            else if (a[i]=='G') aa[i+1]=2;
            else if (a[i]=='T') aa[i+1]=3;
        for (i=0;i<=lb-1;i++)
            if (b[i]=='A') bb[i+1]=0;
            else if (b[i]=='C') bb[i+1]=1;
            else if (b[i]=='G') bb[i+1]=2;
            else if (b[i]=='T') bb[i+1]=3;
        for (i=0;i<=la;i++) for (j=0;j<=lb;j++) f[i][j]=-2147483647;
        f[0][0]=0;
        for (i=1;i<=lb;i++) f[0][i]=f[0][i-1]+d[bb[i]][4];
        for (i=1;i<=la;i++) f[i][0]=f[i-1][0]+d[aa[i]][4];       
        for (i=0;i<=la;i++)
            for (j=0;j<=lb;j++){
                if (f[i][j]+d[aa[i+1]][4]>f[i+1][j]) f[i+1][j]=f[i][j]+d[aa[i+1]][4];
                if (f[i][j]+d[bb[j+1]][4]>f[i][j+1]) f[i][j+1]=f[i][j]+d[bb[j+1]][4];
                if (f[i][j]+d[aa[i+1]][bb[j+1]]>f[i+1][j+1]) f[i+1][j+1]=f[i][j]+d[aa[i+1]][bb[j+1]];
            }
        printf("%d\n",f[la][lb]);
    }
}

[动态规划] pku1338 技巧

Leave a Comment2007.10.09 21:53　by Felicia　

非常经典的递推计算。基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
具体实现见代码。

下面是我的代码

下载: pku1338.cpp
#include <stdio.h>
int u[2000],i,n,p2,p3,p5;
int main() {
    p2=p3=p5=u[1]=1;
    for (i=2;i<=1500;i++) {
        if (u[p2]*2<u[p3]*3 && u[p2]*2<u[p5]*5) u[i]=u[p2++]*2;
        else if (u[p3]*3<u[p2]*2 && u[p3]*3<u[p5]*5) u[i]=u[p3++]*3;
        else if (u[p5]*5<u[p2]*2 && u[p5]*5<u[p3]*3) u[i]=u[p5++]*5;
        else if (u[p2]*2==u[p3]*3 && u[p2]*2<u[p5]*5) u[i]=u[p2++]*2,p3++;
        else if (u[p2]*2==u[p5]*5 && u[p2]*2<u[p3]*3) u[i]=u[p2++]*2,p5++;
        else if (u[p3]*3==u[p5]*5 && u[p3]*3<u[p2]*2) u[i]=u[p3++]*3,p5++;
        else if (u[p2]*2==u[p3]*3 && u[p3]*3==u[p5]*5) u[i]=u[p2++]*2,p3++,p5++;
    }
    while (scanf("%d",&n),n!=0) printf("%d\n",u[n]);
    return 0;
}

[动态规划] pku3420 状态压缩+快速矩阵乘法

Leave a Comment2007.10.08 9:19　by Felicia　

经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有231。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。

下面是我的代码

下载: pku3420.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-6 11:05:55
File Name: pku3420.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
 
int g[16][16];
int M;
 
void dfs(int old_state, int now, int new_state)
{
    if (now > 3)
    {
        g[old_state][new_state]++;
        return;
    }
    if (old_state & (1 << now))
        dfs(old_state, now + 1, new_state);
    if (now <= 2)
    {
        if ((old_state & (1 << now)) == 0 && (old_state & (1 << (now + 1))) == 0)
            dfs(old_state, now + 2, new_state);
    }
    if ((old_state & (1 << now)) == 0)
        dfs(old_state, now + 1, new_state | (1 << now));
}
 
void mul(int a[16][16], int b[16][16], int c[16][16])
{
    for (int i = 0; i < 16; i++)
        for (int j = 0; j < 16; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < 16; k++)
                c[i][j] += a[i][k] * b[k][j];
            c[i][j] %= M;
        }
}
 
int calc(int n)
{
    int p[16][16];
    memcpy(p, g, sizeof(p));
    
    int ans[16][16], tmp[16][16];
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i < 16; i++)
        ans[i][i] = 1;
 
    while (n)
    {
        if (n & 1)
        {
            mul(ans, p, tmp);
            memcpy(ans, tmp, sizeof(tmp));
        }
        n >>= 1;
        mul(p, p, tmp);
        memcpy(p, tmp, sizeof(tmp));
    }
    return ans[0][0];
}
 
int main()
{
    memset(g, 0, sizeof(g));
    for (int i = 0; i < 16; i++)
        dfs(i, 0, 0);
    
    int n;
    while (scanf("%d%d", &n, &M), n + M != 0)
    {
        printf("%d\n", calc(n));
    }
    return 0;
}

[动态规划] pku1191 三维DP

Leave a Comment2007.10.08 9:12　by Felicia　

不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) — (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。

下面是我的代码

下载: pku1191.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-1 19:01:11
File Name: pku1191.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
 
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
 
int n;
int a[9][9], g[9][9];
int f[16][9][9][9][9];
 
inline int sum(int x1, int y1, int x2, int y2)
{
    return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1])
        * (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
}
 
int dp(int k, int x1, int y1, int x2, int y2)
{
    if (f[k][x1][y1][x2][y2] != maxint)
        return f[k][x1][y1][x2][y2];
    if (k == 1)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    if (x1 == x2 && y1 == y2)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    int ret = maxint;
    for (int i = x1; i < x2; i++)
    {
        ret <?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
        ret <?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
    }
    for (int i = y1; i < y2; i++)
    {
        ret <?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
        ret <?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
    }
    return f[k][x1][y1][x2][y2] = ret;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            scanf("%d", &a[i][j]);
    memset(g, 0, sizeof(g));
 
    for (int i = 0; i <= 8; i++)
        for (int j = 0; j <= 8; j++)
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + a[i][j];
    
    for (int k = 0; k <= 15; k++)
        for (int x1 = 1; x1 <= 8; x1++)
            for (int y1 = 1; y1 <= 8; y1++)
                for (int x2 = 1; x2 <= 8; x2++)
                    for (int y2 = 1; y2 <= 8; y2++)
                        f[k][x1][y1][x2][y2] = maxint;
    
    double sum = 0.0;
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            sum += a[i][j];
    sum /= n;
    sum *= sum;
 
    printf("%.3lf\n", sqrt(dp(n, 1, 1, 8, 8) / double(n) - sum));
    return 0;
}
« Older Entries