pku acm 2521 超级水题啊

三月 17, 2009 at 8:16 上午 · Filed under 小心有电

又是那个老板卖东西收假钞的故事。
一个简单的公式：老板收益=收到的钱-商品成本-假钞-找零
不多说直接贴代码：

#include <iostream>
using namespace std;
int main()
{
    long n,m,p,c;
    while(cin>>n)
    {
                 cin>>m;
                 cin>>p;
                 cin>>c;
                 if ((n==m) &amp;&amp; (m==p) &amp;&amp; (p==c) &amp;&amp; (n==0)) break;
                 cout<<n+p-m<<endl;
    }

    return 0;
}

收藏、分享这篇文章！

评论

pku acm 1080 动态规划、编辑距离及其他

三月 17, 2009 at 6:55 上午 · Filed under 小心有电

#include <iostream>
#include <string>
int t(char first,char second)
{
if (first==second &amp;amp;&amp;amp; first!=' ') return 5;
else
{
if ((first=='A' &amp;amp;&amp;amp; second=='C')||(first=='C' &amp;amp;&amp;amp; second=='A')) return -1;
if ((first=='A' &amp;amp;&amp;amp; second=='G')||(first=='G' &amp;amp;&amp;amp; second=='A')) return -2;
if ((first=='A' &amp;amp;&amp;amp; second=='T')||(first=='T' &amp;amp;&amp;amp; second=='A')) return -1;
if ((first=='C' &amp;amp;&amp;amp; second=='G')||(first=='G' &amp;amp;&amp;amp; second=='C')) return -3;
if ((first=='C' &amp;amp;&amp;amp; second=='T')||(first=='T' &amp;amp;&amp;amp; second=='C')) return -2;
if ((first=='G' &amp;amp;&amp;amp; second=='T')||(first=='T' &amp;amp;&amp;amp; second=='G')) return -2;
if ((first=='A' &amp;amp;&amp;amp; second==' ')||(first==' ' &amp;amp;&amp;amp; second=='A')) return -3;
if ((first=='C' &amp;amp;&amp;amp; second==' ')||(first==' ' &amp;amp;&amp;amp; second=='C')) return -4;
if ((first=='G' &amp;amp;&amp;amp; second==' ')||(first==' ' &amp;amp;&amp;amp; second=='G')) return -2;
if ((first=='T' &amp;amp;&amp;amp; second==' ')||(first==' ' &amp;amp;&amp;amp; second=='T')) return -1;
}
if (first==' ' &amp;amp;&amp;amp; second==' ') return 100;
}
using namespace std;
int main()
{
int times,m,n,f[101][101],a,b,c,k,i,j,I,J;
char one[101],two[101];
cin>>times;
for (k=0;k<times;k++)
{
cin>>m;
for (i=1;i<=m;i++)cin>>one[i];
cin>>n;
for (i=1;i<=n;i++)
cin>>two[i];

for (i=0;i<=m;i++) for (j=0;j<=n;j++) f[i][j]=0;
f[0][0]=0;
for (i=1;i<=m;i++) f[i][0]=f[i-1][0]+t(one[i],' ');
for (i=1;i<=n;i++) f[0][i]=f[0][i-1]+t(' ',two[i]);

for (i=1;i<=m;i++)
{for (j=1;j<=n;j++)
{
if (one[i]!=two[j])
{
a=f[i-1][j-1]+t(one[i],two[j]);
b=f[i-1][j]+t(one[i],' ');
c=f[i][j-1]+t(' ',two[j]);
f[i][j]=a>b&amp;amp;&amp;amp;a>c?a:(b>c?b:c);
}
else f[i][j]=f[i-1][j-1]+t(one[i],two[j]);
}
}
cout<<f[m][n]<<endl;
}
return 0;
}

动态规划类的问题往往被归结为水题，不过这是在这题被挂上了可用动态规划解的标签之后。事实上看出最优子结构并找出重叠子结构还是比较有技巧性的，多看看理论著述会有些帮助。

收藏、分享这篇文章！

评论

pku acm 2304 囧死了

三月 5, 2009 at 10:28 下午 · Filed under 小心有电

请各位解题同仁牢牢记住这只锁，丫是里面不转外面转的。这个就是pku 2304的全部难点！

附上脑残代码

#include <iostream>
using namespace std;
int main()
{
int init,n1,n2,n3,deg;
while (cin>>init>>n1>>n2>>n3)
{
if (((n1==n2) &amp;&amp; (n2==n3)) &amp;&amp; (n1==0)) {break;}
//first
deg=720;
if (n1>init) deg=deg+360-(n1-init)*9;
else deg=deg+(init-n1)*9;
//cout<<deg<<endl;
//second
deg=deg+360;
if (n2>n1) deg=deg+(n2-n1)*9;
else deg=deg+360-(n1-n2)*9;
//cout<<deg<<endl;
//third
if (n3>n2) deg=deg+360-(n3-n2)*9;
else deg=deg+(n2-n3)*9;
cout<<deg<<endl;
//cout<<n1<<"  "<<n2<<"  "<<n3<<endl;

}
return 0;
}

收藏、分享这篇文章！

评论